Rendering Forms in a Paragraph

Posted by Christopher Wojno Mon, 14 Jul 2008 19:16:00 GMT

Here’s an example:

<p>If you're looking for other confidential
search parameters, click
<form action="secret_search" method="post">
<input type="hidden" value="my secret search parameters"/>
<input type="submit" value="here"/>
</form>
!</p>

You can’t.

That means you’re stuck with a line-break if you want to have buttons with form data in your paragraphs.

Posted in How-Tos | Tags break, form, html, line, paragraph | 2 comments

Extending Ruby: The Sorted Array

Posted by Christopher Wojno Mon, 23 Jun 2008 20:14:00 GMT

I’ve been working on my personal projects and I came across a problem with the ruby Array class. I have an array containing approximately 500 elements. I need to find each element approximately 500 times ( O(n^2) as the array search is linear ). As you can guess, it takes about 0.5 seconds for all these searches. I figured, if the linear time is 0.5, the binary search taking log_2(n) should take significantly less time to perform.

Attempt #1: A ruby Sorted Array

I first attempted to make a sorted array class in pure ruby. While creation of the class was easy, it was not as efficient as hoped. As a matter of fact, according to my tests, the original ruby Array’s find_index was twice as fast as mine on average. In fact, in order for my set to be as efficient as the original Array, the value being sought had to be over 4/5 the way into the array. Only after that point did my SortedArray overtake the Array in speed. Clearly, this was not the way to go.

After several attempts at re-working and simplifying the loop, I decided that the only reason the Array was so fast, was because it was written natively in C, not ruby.

Attempt #2: A native C ruby Sorted Array

Most of the guiding code to the Sorted Array is from the Pragmatic Ruby Programmer’s Guide: Extending Ruby.

The C-file

First, we start with a new project tree, a-la SVN (this isn’t too terribly important, but I prefer it). Next, we create the first file: sorted_array.c.

In it I included the required ruby file: ruby.h. Next, I went to the subversion repository for the Array code. I’m using the 1.9.0.2 tag.

Take a good look at array.c. I’s packed full of goodness. Unfortunately, I’ll need to copy most of the code so that it supports all the functions we’re used to with the standard Array (though, some cannot be used with this version, such as insert).

There, we now have a fully functional SortedArray that doesn’t sort. It’s a good start.

Turning a normal Array into a SortedArray

The standard Array and the SortedArray are essentially the same. The exception is that all insertions should be made in such a fashion as to preserve the ordering of the elements, that a special constructor be provided to accept un-natural sorting functions, and that searches can be optimized to take advantage of the knowledge of the arrangement of data.

The c-version of the Array has 3 major components in the data structure: length (len), ptr (the start of the array in memory), and aux. Aux has lots of things that support the array, such as the capacity. Keep these in mind when mucking with the internals.

Remap the names

We can’t just use the code as is. Let’s rename all the functions from “rb_ary.

*

*

Enter the Constructors

One of the constructors takes a variable argument list as the 2nd and above parameters. We need to correct this as it simply inserts values. We need to push each individual element. Yes, this will slow down the construction of these types of arrays, but again, we’re banking on searching being the primary operation, not construction.

My version of array.c (1.9.0.2) looks like this:

VALUE
rb_ary_new3(long n, ...)
{
    va_list ar;
    VALUE ary;
    long i;

    ary = rb_ary_new2(n);

    va_start(ar, n);
    for (i=0; i<n; i++) {
    RARRAY_PTR(ary)[i] = va_arg(ar, VALUE);
    }
    va_end(ar);

    RARRAY(ary)->len = n;
    return ary;
}

It needs a little bit of changing. Let’s change: RARRAY_PTR(ary) line to: “rb_sorted_ary_push(ary,va_arg(ar,VALUE));” That should fix it’s wagon. It’s a variable array, so we need to use the c-library variable argument accessors: va_arg and cast it to Ruby’s VALUE type. After that, we just push it to the array, one at a time.

As you may have guessed, I’ve decided to make the primary changes to push and delegating all insertion to that method. We’ll get to this later, however.

Next, we tackle the new4 function. This is the “copy-constructor” if you’re used to C++. Essentially, it is expecting an array passed in as the second parameter (“elts” in my version). The C-code makes a straight copy form a C-array (not a ruby Array!). However, this is not possible if the incoming array is not sorted. We need to insert them one at a time, inserting each. Originally, it looks like this:

VALUE
rb_sorted_ary_new4(long n, const VALUE *elts)
{
    VALUE ary;

    ary = rb_sorted_ary_new2(n);
    if (n > 0 && elts) {
    MEMCPY(RARRAY_PTR(ary), elts, VALUE, n);
    RARRAY(ary)->len = n;
    }

    return ary;
}

The if statement is assuring that the incoming array is not empty or null (nil). That’s a good check and we’ll keep it. But we need to augment it. We know how long the array is, so let’s just iterate through each and push the values onto the array. I threw away the MEMCPY and replaced it with:

for(long i = 0; i < n; ++i) {
  rb_sorted_ary_push( ary, elts[i] );
}

That does it for the constructors (for now, we still need to add a way to provide an unnatural sorting Proc call, but we’ll come back to this later after a bit of testing).

ary_make_* and ary_.* functions

There are two functions that do not adhere to the rb_ary_.* syntax: ary_make_shared and ary_make_hash. Stick a “sorted_” in front of those definitions and in every place they are used.

Do the same with ary_.* functions (such as ary_new and ary_alloc and ary_shared_first). You can do this by simply using vim to search for ”\<ary_” and it will locate any ary_ that has a space or nothing before it (starts a “word”).

to_ary

Keep them as is. I see no need to convert to a sorted array, as we may need to add a parameter to take in a custom sort function (which we’re coming back to later).

Initialize

We now hit the initialize function. It has 4 forms:

1. Array.new(size=0,obj=nil)
2. Array.new(array)
3. Array.new(size) {|index| block}

The first is easy: create an array of size, size, and then fill it with objects given in obj. This version requires no sorted, as all objects will be the same. The second version requires a bit of changing. We need to push each value of the incoming array one at a time to ensure consistency. Jump down to rb_sorted_ary_replace.

The Replacement Detour: before fixing initialize

VALUE
rb_sorted_ary_replace(VALUE copy, VALUE orig)
{
    VALUE shared;
    VALUE *ptr;

    orig = to_ary(orig);
    rb_sorted_ary_modify_check(copy);
    if (copy == orig) return copy;
    shared = sorted_ary_make_shared(orig);
    if (!ARY_SHARED_P(copy)) {
    ptr = RARRAY(copy)->ptr;
    xfree(ptr);
    }
    RARRAY(copy)->ptr = RARRAY(orig)->ptr;
    RARRAY(copy)->len = RARRAY(orig)->len;
    RARRAY(copy)->aux.shared = shared;
    FL_SET(copy, ELTS_SHARED);

    return copy;
}

They simply make a copy of the array’s pointer and declare the source array to be shared. Since we’re not sharing the array, there’s no need to do this anymore, yank out the make_shared line, the line at sets the aux.shared to shared, and the FL_SET. Next, we’ll yank out the pointer and length copying. Since we’re replacing our contents, we need to drop the old contents. Simply drop that if-statement around the xfree(ptr); line, and that will be taken care of. We’ll convert it to a for-loop, iterating through the original, don’t forget to use Ruby’s handy macros! To save some work, I’ll re-use the existing “constructor:”

VALUE
rb_sorted_ary_replace(VALUE copy, VALUE orig)
{
    VALUE shared;
    VALUE *ptr;

    orig = to_ary(orig);
    rb_sorted_ary_modify_check(copy);
    if (copy == orig) return copy;
        ptr = RARRAY(copy)->ptr;
        xfree(ptr);
        // create a new array
        long len = RARRAY_LEN(orig);
        if( len == 0 ) len++;
        RARRAY(copy)->ptr = ALLOC_N(VALUE, len);
        RARRAY(copy)->len = 0;
        RARRAY(copy)->aux.capa = len;
        for( int i = 0; i < RARRAY_LEN(orig); ++i ) {
            rb_sorted_ary_push(copy,RARRAY(orig)->ptr[i]);
        }

    return copy;
}

OK, this is probably the most confusing part so far. Why did we throw away the shared? Ruby cheats because instead of making a true, deep copy of the array it’s making a copy of, it declares the contents of the array as “shared” and simply copies pointers. We can’t do that as we need to re-arrange our data. So that’s why I yanked all the code related to sharing. So now, each object remains unlinked as far as the garbage collector is concerned. Yes, this does make things slower, and yes, does double the memory usage. But we can’t modify the incoming array as it may not be intended to be sorted. So we’re stuck. Because we’re doing a replacement, it’s best to just start from scratch. We do this by freeing up the c-array pointer, using xfree. Next, we get the length of the original array. We then use this to size-up our copy. Why do I add 1 in the case that the length is zero? Because, allocating an array of size 0 will cause C to throw a fit. So, we avoid that mess entirely by creating a starting array with 1 place to store things, but it is empty. We create the appropriately sized, internal c-array. We then set the size of the array to zero to spoof a blank array. We then set the capacity, to tell the Array that it need not resize itself when pushing the next set of items, one at a time.

When all items are added, the array will have the correct length (no longer zero, if the original wasn’t empty).

Back to Initialize to finish the last case

Back to the “initializer,” we now need to take care of the strange case that uses the block to initialize the array, based on the index. We cannot assume that the values created by this block will always be in order. So, after each generation (rb_yield), we need to push them onto the array as usual. The line looks like: “rb_sorted_array_store(ary, i, rb_yeild(LONG2NUM))”. Simply yank that line, and the line incrementing the length (as the length will be modified by the push function). Replace those lines with: “rb_ary_push(ary, rb_yield(LONG2NUM));” That should fix initialize.

Next, the rb_sorted_ary_s_create needs to be changed to, you guessed it, use push. Drop the length and the MEMCPY and insert the for loop, with the push call:

static VALUE
rb_sorted_ary_s_create(int argc, VALUE *argv, VALUE klass)
{
    VALUE ary = sorted_ary_alloc(klass);

    if (argc < 0) {
    rb_raise(rb_eArgError, "negative array size");
    }
    RARRAY(ary)->ptr = ALLOC_N(VALUE, argc);
    RARRAY(ary)->aux.capa = argc;
        for( int i = 0; i < argc; ++i ) {
            rb_sorted_ary_push(ary, argv[i] );
        }

    return ary;
}

Guessing an index

Next, we need to fix up push to stop simply appending. But before that, we need to create a special function to guess an index. Why guess? Because the value may not yet exist, but if it did, this is the index where it would be located in the array. This will be the basic function for both searching, deleting, and pushing.

I’ll call my new function: rb_sorted_ary_guess_index(VALUE ary, VALUE item). Not very creative, but very descriptive. Here’s the problem though: we want to be able to use both natural, and unnatural sorting algorithms. And, either is fine, so long as the ordering is monotonic (goes one-way and is predictable). Before we get into that, let’s just assume we’re using natural ordering, for simplicity. I wrote the following code:

Head up to sorted_array_alloc. Hmmm…. We need to add something to our arrays! We need to store the optional sort-by block!

The Sort-by block

Create a new file called “sorted_array.h”. Create the data structure:

#include "ruby.h" 

struct RSArray {
    struct RBasic basic;
    long len;
    union {
        long capa;
        VALUE shared;
    } aux;
    VALUE *ptr;
    ID cmp;
};

This is an exact duplicate of the RArray in ruby.h. The only exception is the additional ID *cmp, our comparison function. Be sure you’ve included this structure file in the sorted_array.c file.

Back in the sorted_array.c file, make sure you cap the new cmp variable with a NULL in sorted_ary_alloc: ary->cmp = NULL; Just put it under the aux.capa assignment. Now, we need to “fix” the sort_2 function to fall-back to the default comparison function, but to prefer a specified function if given. Let’s create a class-specific sort function called: sorted_array_sort_3.

Posted in Ruby Snippets | Tags array, c, efficient, extend, extending, lookup, native, ruby, sorted | no comments

Theoretical Sets

Posted by Christopher Wojno Sat, 31 May 2008 19:46:00 GMT

Recently, I have been thinking about a particular data structure that I’ve never seen before. For those who do not know, I am an avid C/C++ programmer and have recently discovered Ruby and Rails. Thus, I am familiar with the STL that is so closely related to C++. One of my favorite containers is the set. Sets operate just like you’d expect of a mathematical set (thus the name). It contains a set of values.

For example (an assume I have a magical print function to inspect the sets on the terminal):

set<int> my_set;
my_set.insert( 7 );
my_set.insert( 5 );
magic_set_printer( my_set );

{5,7}

As you can see, they’re good for keeping small sets of things.

So What is a Theoretical Set?

The problem with sets as they appear in C++: they require storage space for every item stored in them. This isn’t a big problem if you have only a few elements in a set, but what’s the fun in that? Suppose you have the same set above in Figure 1 but decide to add the value 6. Under a normal set, your set will contain the values 5, 6, and 7. Extending the argument, if your set contains a contiguous, uinterrupted set from, say, 5 to 1,000, your set will contain, yes, you guessed it: 995 elements. Clearly, there’s room for some improvement if you expect contiguous values.

Enter the theoretical set.

It is just like a normal STL set, however, it will take shortcuts on memory by combining values into ranges. For example, the set: {5,6,7} becomes: {5..7}. The original set will use 3 values, the theoretical set will use 2. As you can see, if you have a large set from 5..1000, it is better to use the theoretical set as search times and memory will be saved. While I’m not sure, exactly, at what point it becomes more economical to use theoretical sets (and again, it depends on use), if you expect to have contiguous ranges in your sets, I suspect much improved performance.

Unfortunately, operating on ranges is harder than operating on single values. Thus, there is a relatively significant performance penalty when calculating intersections, differences, etc. Though, in the long-run, the penalty is not noticeable.

A Ruby Theoretical Set

I had originally envisioned such a construct to be written for the benefit of C++ coders. However, due to the number constraints, I was dissuaded. Ideally, one should be able to use a theoretical set on any type of number. While templates offer some solution, I also wanted more: complex types.

Should one not be able to arrange a set of contiguous dates? Maybe not contiguous to the second, but perhaps weekends? A set over a range of objects. Makes you tingle a bit, doesn’t it?

The nice thing about loosely typed languages, is that you can pass just about anything into them without worrying much about some of the details. So that solves the typing problems with C++ and makes for a good set!

I have not actually implemented a straight-up Ruby Theoretical Set. I have created on that uses ActiveRecord, but that’s a post for another time.

Posted in Theory | Tags c, set, stl, theoretical | no comments

Rails Unit Testing Fixtures: Scenarios

Posted by Christopher Wojno Fri, 16 May 2008 00:56:00 GMT

I hurriedly wrote an article this morning about my adaptation of fixtures I call sub-fixtures. While it seemed like a good idea in theory, it it beastly to implement in practice. It requires writing new fixtures for every unique test (if used correctly). When used incorrectly, the test names don’t describe the data configuration being tested against.

I sat down and thought about it a little longer. What I really need is a scenario. A database state poised for a particular test. Needless to say: such a scenario is not limited to a single table. That way, the scenario is describing the database state being tested against and can therefore be used logically in other tests as well.

Only one minor change is required. In the test directory, add the following code to the body of the Test::Unit::TestCase class in test_helper.rb:

    def load_scenario( scenario )
        directory = File.dirname(__FILE__)+'/fixtures/scenarios/'+scenario+'/'
        files = Dir.entries( directory )
        files.delete( '.' ); files.delete( '..' )
        exp = /[^\.].*\.(yml|csv)$/
        models = files.select{|f| f[exp] }
        models = models.collect{|m| m.slice(0,m.length-4).to_sym}
        Fixtures.create_fixtures( directory, models )
    end

Again, it requires a special directory structure (maybe I’ll write a scenario generator later). in the test/fixtures I added a new directory: scenarios. Within that directory are other directories containing the scenarios fixture setups. For example, if I want to create a scenario where my list of weekly cookie recipes is missing a cookie and I want to test my code to see if it finds the correct missing cookie, I simply create the following directory:

test/fixtures/scenarios/missing_cookie

And in that directory, I create the following fixture files:

• cookies.yml
• users.yml
• user_cookies.yml

Note: it works for .csv files as well. Simply create the fixtures like you normally would do.

Now, in your unit test code, add the following line to the beginning of your test case method:

load_scenario( 'missing_cookie' )

Now, when your test runs, it will create the scenario in the database that you specify. It will automatically load all the fixture files in the directory.

Problems

Again, if you use normal fixtures, they will be loaded and unloaded (will make testing a little slower).

Posted in Rails Snippets | Tags fixture, scenario, testing, unit | 1 comment

Flexible Fixtures in Rails Unit Tests

Posted by Christopher Wojno Thu, 15 May 2008 19:25:00 GMT

I’ve found that when testing model classes, it’s important to have a database that is setup with records such that something fails or is configured to produces results in a particular way. With the current rails Fixture framework, this is impossible. Let me explain what I’ve been trying to do to give you a better idea of what is lacking in Rails:

Example Problem Description Finding Something That’s “Missing”

Suppose you have a database with a table called “cookies” and another table “users” and another table called “user_cookies.” As you can see, you have a set of users and types of cookies. Maybe the cookies are chocolate or mint, etc. However, these are cookies of the month. Each month, a new cookie is released. To keep track of which month the cookie is for, we include a year and month field in the cookie table. Now, if we have users that want to track which cookies they’ve tried over the course of the years, we need to either keep a list of all the cookies they’ve eaten, or search for holes in the cookie order.

Even if we had a list, say we had a weekly and monthly cookie. If we wanted to know which monthly cookies we’re missing, the list will be of no use as well, as the list cannot differentiate between monthly or weekly. We’re forced to look for holes. Luckily, such a request is rare in our system, so a brute force search will be small (there are ways of making it faster, but that’s beyond the scope of this article).

Rails Testing Framework “Deficiency”

Don’t get me wrong, the testing framework for Rails is well done, easy to use, and mostly comprehensive. However, the Fixture support is a bit lacking. If you want to have multiple types of tests that act on the database records as a whole, you need custom fixtures. For the above problem, we need a fixture to test cookie lookups, but we also need a test to detect missing cookies.

So we need multiple fixtures we can load with different tests. Well, that’s not really possible with the standard testing framework. The class method “fixtures” for Test::Unit::TestCase (the testing base class) will only load up the standard fixtures. Bummer. I want to create subdirectories in the fixtures directory that are named after the model being tested. Within those directories, there will be more directories that name the test in progress. Within THAT directory will be the .yml files for custom database setups.

So the directory structure is of this form:

|-+BASE RAILS APPLICATION
| |-+ test
| | |-+ fixtures
| | | |-+ MODEL_NAMEs
| | | | |-+ test_find_missing_cookies
| | | | | |- users.yml
| | | | | |- cookies.yml
| | | | | |- user_cookies.yml
| | | | |-+ test_find_favorite_cookie
| | | | | |- user_cookies.yml
 ...

Not only can you deploy custom fixtures for models and more than just one, you can also specify tables to populate other than the model with which you’re working. This provides as much flexibility as I can fathom that I need.

But, alas, you need a way to load these fixtures up. Admittedly, my method is a bit messy and slow if you use the traditional Fixtures. You need to modify the test_helper.rb file. Add this to the Test::Unit::TestCase class:

    @@model_name = nil
    def self.fixture_model( m )
        @@model_name = m
    end

    protected
    def load_subfixtures( test_method, pfixture_table_names = [], pfixture_class_names = [] )
        raise StandardError.new( 'load_subfixtures requires that you specify the model name in the class by calling the class method: fixture_model' ) if @@model_name.nil?
        fixture_path = File.dirname(__FILE__) + '/fixtures/'+@@model_name.to_s+'/'+test_method+'/'
        return super unless File.exists?( fixture_path )

        oldpath = fixture_path
        oldtables = fixture_table_names
        oldclasses = fixture_class_names
        @@fixture_path = fixture_path
        @@fixture_table_names = pfixture_table_names
        if @@fixture_table_names.empty?
            @@fixture_table_names = fixture_table_names
        else
            @@fixture_table_names.push @@model_name
        end
        @@fixture_class_names = pfixture_class_names
        @@fixture_class_names = fixture_class_names if @@fixture_class_names.empty?
        oldret = load_fixtures
        @@fixture_path = oldpath
        @@fixture_table_names = oldtables
        @@fixture_class_names = oldclasses

        return oldret
    end

As you can see, it does not override the fixture initializer for the unit tests. It merely calls it again. Here’s how you use it:

require File.dirname(__FILE__) + '/../test_helper'

class UserCookieTest < Test::Unit::TestCase
  fixture_model :user_cookies

  # Replace this with your real tests.
  def test_find_missing_cookies
        load_subfixtures( 'test_find_missing_cookies', [:users,:cookies] )
        assert_equal 2, UserCookie.count
  end
end

For the test: test_find_missing_cookies, it will load up the .yml files: user_cookies.yml, cookies.yml, and users.yml for use with that test.

You need to specify the fixture_model as this is the directory it will look in for additional sub-fixtures. If you don’t the call will fail with an exception.

Problems

Obviously, it’s not very smart. It can’t automatically detect the test name. Though, this allows you to re-use fixtures from other tests as well as mix and match the sub-fixtures loaded with the test. But it requires that you manually type in the test name for every test.

In addition, if the fixture has already been loaded using the standard class method call: fixtures, it will be loaded and overwritten by the test a second time. This will slow the testing process down.

I’m happy with it. I bet you’ve been waiting for something like this too. Enjoy!

Edit

An update to this article is posted here.

Posted in Rails Snippets | Tags fixture, test, unit | no comments

Secret Group Handshakes Paper

Posted by Christopher Wojno Tue, 13 May 2008 23:15:00 GMT

For my security class, I chose to author my extended abstract concerning secret group handshakes. Though not intended to be a research paper, it covers the basic aspects of how secret handshakes are done, why they’re useful, and some security weaknesses inherent in the common approaches.

Abstract

“Secret groups, while preserving the anonymity of the members, have a multitude of applications. Discussed here are the fundamentals of a relatively new approach to anonymity called a secret handshake and the key concepts preserving that secrecy. Following an explanation of the mechanics of two and multi-party handshakes, open problems are presented and future research directions are suggested.”

Read the paper

Posted in Security | Tags bilinear, diffie, group, handshake, hellman, paper, secret | no comments

Microsoft and Spam

Posted by Christopher Wojno Sat, 12 Jan 2008 21:57:00 GMT

Today, I received and e-mail from a hotmail account explaining how I won a prize. It’s a clone of the English lottery scam, but the supposed Microsoft Award Team is listed as the sender. I figured I’d do the responsible thing and forward it off to abuse@microsoft.com. However, I was shocked when I received the following reply from MY mail server:

This is the mail system at host mail.adtrackersolutions.com.

I'm sorry to have to inform you that your message could not
be delivered to one or more recipients. It's attached below.

For further assistance, please send mail to postmaster.

If you do so, please include this problem report. You can
delete your own text from the attached returned message.

                  The mail system

<abuse@microsoft.com>: host maila.microsoft.com[131.107.115.212] said: 550
   5.7.1 <Your e-mail was rejected by an anti-spam content filter on gateway
   (131.107.115.212). Reasons for rejection may be: obscene language,
   graphics, or spam-like characteristics. Removing these may let the e-mail
   through the filter.> (in reply to end of DATA command)
Reporting-MTA: dns; mail.adtrackersolutions.com
X-Postfix-Queue-ID: 7718A48041
X-Postfix-Sender: rfc822; cwojno@.com
Arrival-Date: Sat, 12 Jan 2008 10:13:25 -0800 (PST)

Final-Recipient: rfc822; abuse@microsoft.com
Action: failed
Status: 5.7.1
Remote-MTA: dns; maila.microsoft.com
Diagnostic-Code: smtp; 550 5.7.1 <Your e-mail was rejected by an anti-spam
   content filter on gateway (131.107.115.212). Reasons for rejection may be:
   obscene language, graphics, or spam-like characteristics. Removing these
   may let the e-mail through the filter.>

From: Christopher Richard Wojno <cwojno@.com>
Date: January 12, 2008 10:13:20 AM PST
To: abuse@microsoft.com
Subject: Fwd: CONGRATULATION!!!

OK, so I can’t tell Microsoft about spam because their spam filter refuses my message? That’s really stupid.

Posted in Sob Stories | Tags microsoft, refused, spam | 2 comments

A DNS Server to Call My Own

Posted by Christopher Wojno Sun, 30 Dec 2007 23:56:00 GMT

I’ve been itching to set up my own DNS server for a while now. Why? I’ve come up with three reasons:

1. Speed
2. Convenience
3. Security

The first one is pure fluff. My home network doesn’t have nearly enough traffic to make it worth it. The second has merit. It would be nice if I could name machines on the network and have them resolve correctly. I could also use it to mask external addresses. So I could make stuff up and have it resolve locally. So I could make, oh, doubleclick.net resolve to 127.0.0.1. Now, no one on my network will get those advertisements anymore. Sure, I have it set up in the hosts file now, but I’m like any other network administrator… No, not lazy, but clever.

I’m working with Linux Gentoo 2.6.19 here on my local network. There is no chance that I will corrupt any legitimate records as nobody outside my network will be able to query my DNS server. I have my favorite editor: Vim at my side. Named (Bind) is currently at version BIND 9.4.1-P1.

Install bind

First, edit your /etc/portage/packages.use file. Add a line that says:

net-dns/bind -ipv6 -ldap postgres -ssl threads -mysql -bind-mysql -odbc

This means: I don’t want IPV6 support (my router doesn’t support it… sadly). Don’t use ldap. Add support for postgres (my favorite database). Don’t include SSL support (I’m assuming everyone trusts my server on the local network). Use threads to handle many requests simultaneously (I suppose I could turn this off as the server load will not be very large). Finally, don’t include mysql bindings or ODBC. Save that file.

Emerge

Using Gentoo’s emerge system:

%emerge net-dns/bind

It should install without any further intervention.

Firewall (IPTables)

I use the IPTables firewall to protect my server from local and foreign attacks. I like it because it gives me a lot of control over what goes in and out. I also don’t like it because it is very complicated. If you have a firewall, you need to poke holes in it for port 53 in the following ways:

1. Outgoing UDP connections TO port 53 from your server to the DNS servers you normally use
2. Incoming UDP connections TO your server on any port from the DNS servers you normally use for established UDP connections
3. Same as #1 with TCP connections
4. Same as #2 with TCP connections
5. Incoming UDP connections from the local network on port 53
6. Outgoing UDP connections to the local network on any port for established UDP connections
7. Same as #5 with TCP connections
8. Same as #6 with TCP connections

The above table is derrived from nixCraft’s article: Linux Iptables block or open DNS / bind service port 53 I added some modifications, however. Here’s an example configuration:

firewall.sh

#!/bin/bash
IPTABLES='/sbin/iptables'
LOCALNET='--src-range 192.168.1.2-192.168.1.254'
INTIF1='eth0'
DNSSERVERS='a.b.c.d a.b.c.e' # 2 IP addresses for your ISP's DNS servers

# PREAMBLE
$IPTABLES -F #flush old rules
$IPTABLES -X #clear old chains
$IPTABLES -A INPUT -s 127.0.0.1 -j ACCEPT #always trust requests from the server
$IPTABLES -A INPUT -m state --state RELATED,ESTABLISHED -j ACCEPT #always trust active connections

# ... (other rules here)

# BIND/NAMED
# Outgoing Recursive Requests
for ip in $DNSSERVERS
do
        iptables -A OUTPUT -p udp -d $ip --dport 53 -m state --state NEW,ESTABLISHED -j ACCEPT
        iptables -A INPUT -i $INTIF1 -s $ip -p udp --dport 53 -m state --state ESTABLISHED -j ACCEPT
        iptables -A OUTPUT -p tcp -d $ip --dport 53 -m state --state NEW,ESTABLISHED -j ACCEPT
done
# incoming request configuration
# accept local queries
iptables -A INPUT -i $INTIF1 -m iprange $LOCALNET -p udp --dport 53 -m state --state NEW,ESTABLISHED -j ACCEPT

# block out all other Internet access
$IPTABLES -A INPUT -j DROP

The for loop was nixCraft’s idea. Very clever, however, instead of using the IP address of the server, I fell back to the interface card. Then, no matter what your IP address, you’ll be able to control access to the DNS server.

Update your firewall rules by executing your firewall script.

%./firewall.sh

IPTables example explained

This example actually works as is. But if you’re using SSH for access, you need to add in an SSH hole:

$IPTABLES -A INPUT --protocol tcp --dport 22 -j ACCEPT

Now, the beginning of the script defines (in order) the script used to interpret the file (#!/bin/bash), the iptables program (stored as a variable for ease in name or location changes), LOCALNET (an IP address range specifying your local network, generally, 192.168.1.1 is the gate way and packets may appear to originate from your router if it’s a piece of junk. 192.168.1.255 is broadcast, so no need to include that address either), INTIF1 is the NIC card on my server. Use ifconfig to figure out what yours is (or iwconfig if you have a wireless server because you’re crazy that way). Next, I define the DNS servers from my ISP. I didn’t list them here because my ISP probably would not appreciate that. Use OpenDNS if you’re really in a bind (pun not intended).

Let’s skip to the #BIND/NAMED section. Here, I’ve looped through each DNS server from my ISP. I’ve opened up the UPD and TCP ports to allow recursive look ups generated by my local network traffic. After that loop, I open up port 53 locally. Notice I’ve used the interface (-i #INTIF1). This restricts where requests may originate. You really only need this if you have more than one NIC card on the box.

Configuration

Before we can test, there’s one more thing we need to do: configure named/bind to listen to us. By default, bind is configured to only accept connections made ON THE SERVER. That doesn’t help when you want other computers on your network to be able to make requests. Open: /etc/bind/named.conf in vim. You need to change the listen-on directive to include your local network address. I just used “any” as my firewall will deny any other requests.

...
options {
  /* ... other configurations here ... */
  listen-on {any;};
};

Make sure you include the semi-colon after “any” or you’ll get named complaining at you. Restart named (bind).

%sudo /etc/init.d/named restart

Testing your server

You should now be able to test DNS lookups from another machine. From you local (non-DNS server), type:

%dig @DNSSERVER_IP_ADDRESS www.google.com

; <<>> DiG 9.4.1-P1 <<>> @DNSSERVER_IP_ADDRESS www.google.com -t A
; (1 server found)
;; global options:  printcmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 13465
;; flags: qr rd ra; QUERY: 1, ANSWER: 5, AUTHORITY: 7, ADDITIONAL: 0

;; QUESTION SECTION:
;www.google.com.            IN    A

;; ANSWER SECTION:
www.google.com.        604748    IN    CNAME    www.l.google.com.
www.l.google.com.    249    IN    A    64.233.169.104
www.l.google.com.    249    IN    A    64.233.169.103
www.l.google.com.    249    IN    A    64.233.169.147
www.l.google.com.    249    IN    A    64.233.169.99

If you’re using Windows, you need to use nslookup (command line application). The syntax is slightly different. If you’re using Gentoo, you need to first install the bind tools (emerge net-dns/bind-tools).

That’s it! You now have a working local DNS server merely acting as a cache.

Posted in How-Tos | Tags bind, cache, configure, dns, gentoo, install, linux, named, server, setup | 1 comment

Covert Channel Paper

Posted by Christopher Wojno Sun, 30 Dec 2007 20:07:00 GMT

I wrote a paper for my Operating Systems class this recent semester about covert channels.

Abstract

A thirty year-old problem, covert channels continue to plague the security of modern operating systems. These channels are explained and discussion of the subject is motivated. A short evolution of the problem is given as well as several classifications of covert channels. Several methods such as type enumeration, flow analysis, virtualization, and adding noise are discussed and analyzed. Finally, one system is evaluated in context of those methods and future directions into covert channel research are suggested.

Read more

Posted in Questions, Theory | Tags channels, covert, operating, paper, security, system | no comments

Mac Latex-mk

Posted by Christopher Wojno Sun, 30 Dec 2007 19:27:00 GMT

I really like the LaTeX typesetting system. It makes nice looking documents. It’s a bit of a pain to use, however. On FreeBSD, there is a LIFE-SAVING port called “latex-mk,” which is a set of maintained make files that will do all the heavy-lifting for you. It’s only released for FreeBSD and NetBSD, but I’ll walk you through how to install it on Darwin (Mac). I make no warrantees here. You accept all responsibility for following these instructions or deviating from these instructions. I am not responsible for lost data or damaged property, etc.

Installation

Getting LaTeX and latex-mk

First, you need the latex package for Mac: MacTex. Install that the usual way (or read their instructions if you get lost, no sense me repeating them). Once you have that installed, grab the latex-mk file. You’ll have to dig around a big, look under “Obtaining” if that link still exists. You’ll see a SourceForge download. Download this file: latex-mk-1.9.1.tar.gz. I’m sure these instructions will work for future versions too, though I make no guarantees.

Uncompressing/Unarchiving

Go ahead and unzip the latex-mk. Crack open a terminal (Finder > Applications > Utilities > Terminal.app). Change to the latex-mk directory:

cd ~/Downloads/latex-mk-1.9.1

If the version has changed, cd to that. Remember, you must unzip it first. Apple’s archiver should handle it. But you can always do a “tar -xzf latex-mk-1.9.1.tar.gz” if you’re old fashioned like me.

Configuration

Like most packages, you need to run the configuration program. Do this from the latex-mk-1.9.1 directory (you should still be there).

sh ./configure

You will see lots of text fly by. If you get errors, sorry, this tutorial is over. Drop me a line, maybe I’ll be able to help or point you in the right direction. If you see it create lots of little files, then you’re golden.

Compile

Type:

make

And, after a very short time, it will complete.

Install

Type

sudo make install

Sudo will ask for an administrator’s password. Enter it. If you don’t trust this package, you can always install by hand… But I’m not going over that. Once this is done, latex-mk is now installed and ready for use.

Cleaning up

Type:

make clean distclean

That will remove any installation files. You may also simply delete the latex-mk-1.9.1 folder. You should delete the zip file from which you got the latex-mk-1.9.1 folder; you no longer need it.

Testing

Let’s take it for a spin. Assuming you have MacTex installed already:

• Create a new folder somewhere, I’ll call it: “Test”
• cd to “Test”
• Create a new latex document, say, “test.tex” and type or copy in the following:

%test.tex:
\documentclass[]{article}
\begin{document}
\LaTeX
\end{document}

• Now create a new file called “Makefile” and put the following into it:

#Makefile
NAME = test
TEXSRCS = test.tex
BIBTEXSRCS = 
TGIFDIRS = tgif_figs

include /usr/local/share/latex-mk/latex.gmk

• At the command prompt, type: “make pdf”
• You’ll see it build the file. When it finishes, open finder and go to your “Test” folder. You’ll see a shiny new “Test.pdf” so go ahead, click it! You’ll see the strangely formatted LaTeX logo.

Congratulations. You just “ported” a FreeBSD application to Mac. Aren’t command line applications grand?

Why Latex-mk?

Latex-mk takes care of lots of details when creating LaTeX documents. It keeps your bibliography up to date automatically and will re-run the latex processor to ensure all your citations and cross references are up to date and shiny. Otherwise, you have to run latex 2-3 time every change to ensure your references will be linked. Your new friend is “make pdf” as it enables one-stop generation shopping.

More Information

The make file can do much more. You should see what it can do by going to the latex-mk site for instructions.

Posted in How-Tos | Tags freebsd, latex, mac, makefile, mk, port | no comments