Invariant Properties

Edge Nodes and Rolling your own Hadoop Packages

I must answer an important question before I start. Why would anyone want to build Hadoop themselves? Isn’t it much saner to use one of the commercial distributions like Cloudera or Hortonworks? Both have ‘express’ versions that are free to use and ideal for developers and small-scale testing. (They’re distributed as VMWare images but it’s straightforward to convert a VMWare image into an AWS image that can be run on an EC2 instance. In fact it’s an item on my to-blog list!) The Cloudera Express version also has an option that gives you a straight Hadoop cluster without the Cloudera enhancements.

Why bother building our own packages?

The answer is edge nodes. The classic Hadoop environment, e.g., what you’ll see in a Coursera specialization, involves a tidy Hadoop cluster that has map/reduce jobs uploaded to it and run. Everything goes through a handful of clean interfaces.

In practice any site that needs a Hadoop cluster will probably have its own software that solves its business needs and that software uses the Hadoop cluster as a resource no differently than an existing database, mail, or jms service. It needs access to the cluster but only via the well-defined wire protocol. In addition any CISO on the ball will want to keep the Hadoop cluster tucked away on its own locked-down VPC, one that has the Hadoop cluster on it but nothing else. She’ll also want anything that talks to the cluster on a relatively locked-down VPC, ideally one that’s not directly accessible from the corporate VPN much less the internet at large.

Hence ‘edge nodes’. The idea is that a Hadoop cluster consists of two types of nodes. Compute nodes run the actual Hadoop services, edge nodes do not but are able to communicate with the services. They’re often the only way to communicate with the services. Edge nodes can be located in the same VPC as the compute nodes or they can be located in a different VPC. There are benefits and drawbacks to both approaches.

Setting up an edge node is pretty straightforward. Besides access to the Hadoop compute nodes you need:

• The configuration files from the cluster (typically in /etc/hadoop)
• The appropriate client jars from the cluster
• The Hadoop client programs (e.g., ‘hadoop’ or ‘hdfs’) if you’ll do anything from the command line or in scripts
• The shared libraries for native code. (Optional but it improves performance)

In addition you’ll need the Kerberos client apps and the /etc/krb5.conf file if you use Kerberos authentication within the cluster. Kerberos is a good idea even if you’re on a dedicated VPC. The commercial distributions make it easy to set up if you don’t already have a corporate KDC. Again there are benefits and drawbacks to using the KDC bundled in the Hadoop distribution vs. using a corporate KDC.

Developer systems will also often be set up as edge nodes to development-internal clusters.

So Why Do We Need To Build Our Own Packages?

We have commercial distributions. They provide free ‘express’ versions and even a free prebundled standard Hadoop cluster. So why would we possibly want to build our own packages?

There are two reasons. The first is the most obvious – we want or need to use the version of a service that’s not supported by the commercial distribution. Cloudera takes a very conservative approach so even the newest release contains older versions of the services, albeit ones that have often had new features backported to them. Hortonworks takes a more aggressive approach and will have newer versions of the services but there’s no guarantee that it will have the version you need. In these cases you need to provide the tarball yourself and it’s often better to build it locally than to download a prebuilt image in order to reduce the risk of a nasty surprise because of unmet expectations in the system libraries. That’s rare but it can be a real pain to track down when it occurs.

The second reason is more subtle. There’s no requirement that the edge nodes run the same operating system as the compute nodes. This could be a small change, e.g., a developer laptop running Ubuntu vs. a CDH cluster running on RedHat, or it could be more substantial such as a macbook developer laptop. In the case of Ubuntu it should be possible to copy the RedHat files but again rebuilding the packages on your own system ensures there won’t be any surprises.

The Easy (But Incomplete) Solutions

You can built the most recent versions of Hadoop by cloning https://github.com/apache/hadoop and running the start-build-env.sh script. That creates a Docker environment with all of the required libraries so builds will go quickly.

$ git clone https://github.com/apache/hadoop
$ cd hadoop
$ ./start-build-env.sh

Unfortunately that script was introduced in Hadoop 2.8. I need to support earlier versions and that means building Hadoop on the command line instead of a preconfigured Docker container. At first glance this is straightforward:

#
# get source...
#
$ git clone https://github.com/apache/hadoop
$ cd hadoop
$ git checkout release-2.5.0

#
# install development libraries
#
$ sudo apt-get install libopenssl-dev zlib1g-dev libbz2-dev libsnappy-dev

#
# install Kerberos client and development libraries (just in case)
#
$ sudo apt-get install krb5-client, libkrb5-dev

#
# install required tools
#
$ sudo apt-get install cmake protobuf-compiler

#
# build Hadoop distribution tarball including native libraries
#
$ mvn package -Pdist,native -DskipTests -Dtar -Dmaven.javadoc.skip=true -Drequire.snappy -Drequire.openssl

At this point we should fly along… until we do a good impression of a bug hitting a windshield. Ubuntu 16.10 provides version 3.0.0 of the protocol buffer tool but Hadoop has a hard requirement on version 2.5.0. That version hasn’t been supported by Ubuntu since 14.04.

We could manually download and install the 14.04 .deb packages but that runs the risk of getting into library dependency hell. There is a better solution.

Building Protocol Buffers 2.5.0 on Ubuntu 16.10

The solution is a bit of Ubuntu-fu. We don’t want to install the Ubuntu 14.04 binary packages but there’s no problem downloading the Ubuntu 14.04 source package and rebuilding it in our Ubuntu 16.10 environment. We can then safely install these packages as either a direct replacement or in a separate location (using ‘dpkg –root=dir’) without worrying about introducing other outdated libraries.

#
# download source package. There's a way to do this with dpkg-source but with older source packages
# I prefer to do it manually.
#
$ wget https://launchpad.net/ubuntu/+archive/primary/+files/protobuf_2.5.0.orig.tar.gz
$ wget https://launchpad.net/ubuntu/+archive/primary/+files/protobuf_2.5.0-9ubuntu1.debian.tar.gz
$ wget https://launchpad.net/ubuntu/+archive/primary/+files/protobuf_2.5.0-9ubuntu1.dsc

#
# unpack source
#
$ dpkg-source --extract protobuf_2.5.0-9ubuntu1.dsc

#
# build binary packages. this will take awhile.
#
# note: you might need to install additional packages in order to build this package.
# Build dependencies are listed in the control file under "Build-Depends".
#
$ cd protobuf-2.5.0
$ dpkg-buildpackage -us -uc -nc

#
# the binary packages are now available in the original directory. You can install
# them using 'dpkg', or 'dpkg --root=dir' if you want them to exist in parallel with
# the current libraries. In the latter case you will need to specify the new location
# when you build hadoop.
#
$ cd ..
$ sudo dpkg -i *deb

Note: you system will revert to the 3.0.0 version with the next ‘apt-get upgrade’ unless you pin the version at 2.5.0.

Finishing and Deploying the Build

We can now finish the build. When it is done there will be a large .tar.gz file in the hadoop-dist/target directory. For instance hadoop-2.5.0.tar.gz is over 133 MB. This file is traditionally untarred in the /opt directory.

#
# untar package
#
$ sudo tar xzf hadoop-dis/target/hadoop-2.5.0.tar.gz -C /opt

#
# create symlink to make life easier
#
$ cd /opt
$ sudo ln -s hadoop-2.5.0 hadoopk

#
# make the native libraries available
# (note: file must be created as root. showing 'echo' for convenience.)
#
$ echo /opt/hadoop/lib/native > /etc/ld.so.conf.d/hadoop.conf
$ sudo ldconfig

#
# verify shared libraries are now visible
#
ldconfig -p | grep hadoop

#
# add hadoop binaries to PATH. Note: in the long term you'll want to update
# /etc/profile or ~/.bashrc.
#
export PATH=$PATH:/opt/hadoop/bin

#
# set HADOOP_HOME. Or is it HADOOP_COMMON_HOME? HADOOP_PREFIX? This seems to change between
# Hadoop versions so check your documentation.
#

In total the contents of /opt/hadoop include seven directories: bin, etc, include, lib, libexec, sbin, and share. Edge nodes need to keep bin, lib, libexec, share/doc, and the client libraries from share/hadoop. The easiest way to find them is

$ find /opt/hadoop/share/hadoop/common/lib
$ find /opt/hadoop/share/hadoop -name "*-client*-2.5.0.jar"
$ find /opt/hadoop/share/hadoop -name "*-common*-2.5.0.jar"

In my case that’s

• ./common/hadoop-common-2.5.0.jar
• ./common/hadoop-nfs-2.5.0.jar (needed?)
• ./common/lib/hadoop-annotations-2.5.0.jar
• ./common/lib/hadoop-auth-2.5.0.jar
• ./mapreduce/hadoop-mapreduce-client-app-2.5.0.jar
• ./mapreduce/hadoop-mapreduce-client-common-2.5.0.jar
• ./mapreduce/hadoop-mapreduce-client-core-2.5.0.jar
• ./mapreduce/hadoop-mapreduce-client-hs-2.5.0.jar
• ./mapreduce/hadoop-mapreduce-client-hs-plugins-2.5.0.jar
• ./mapreduce/hadoop-mapreduce-client-jobclient-2.5.0.jar
• ./mapreduce/hadoop-mapreduce-client-shuffle-2.5.0.jar
• ./yarn/hadoop-yarn-client-2.5.0.jar
• ./yarn/hadoop-yarn-common-2.5.0.jar
• ./yarn/hadoop-yarn-server-common-2.5.0.jar (needed?)

plus a large number of third-party libraries. Some of the less common ones that are unlikely to already be in your app include

• ./common/lib/apacheds-i18n-2.0.0-M15.jar
• ./common/lib/apacheds-kerberos-code-2.2.0-M15.jar
• ./common/lib/avro-1.7.4.jar
• ./common/lib/guava-11.0.2.jar
• ./common/lib/jsch-0.1.42.jar
• ./common/lib/paranamer-2.3.jar
• ./common/lib/protobuf-java-2.5.0.jar
• ./common/lib/psnappy-java-1.0.4.1.jar
• ./common/lib/zookeeper-3.4.6.jar

We don’t need the contents of the /opt/hadoop/etc directory – we should use a copy of the configuration files from one of the compute nodes. We don’t need the contents of the include, sbin, or rest of the shared directories since they are only required when we run the Hadoop services.

Distribution

We don’t need to go through this process on every edge node – in the case of Ubuntu it’s easy to create a binary package for redistribution via ‘dpkg -b’. We have to follow a few simple rules and we’ll have a package that can be safely installed, updated, and removed. One huge benefit of using a binary package is that we can safely put the files in their standard places instead of the /opt directory.

I’m not familiar with the RPM creation process but I’m sure it’s equally easy to do in that environment.

Finally I am debating debating creating a Debian/Ubuntu PPA with these packages for multiple Hadoop projects and versions. Watch this blog for announcements.

Other Hadoop Projects

There are other Hadoop projects that we will want to bundle for edge nodes. One good example is Hive – building the package from source gives us the ‘beeline’ and ‘hplsql’ command line tools. The process should go smoothly once you have an environment that can build the main Hadoop project. Just be careful to examine the pom file since available profiles and final distribution location will differ.

I haven’t been posting since I’ve been very busy learning Hadoop + Kerberos for multiple client environments and getting into shape before it’s too late. (I know it’s “never too late” in principle but I’m seeing family and friends my age who are now unable to do hard workouts due to medical issues. For them it is “too late” to get into better shape so this is no longer an abstract concern for me.)

Part of my broader work is supporting applications with user-provided JDBC drivers. We bundle the datasource (typically HikariCP) and allow the user to specify the JDBC driver jar. Support has been very ad hoc and I’ve been working on parameterized tests that use aether to query the maven central repository for all versions of the datasource and JDBC jars and then verifying that I can make a connection to our test servers using all possible combinations. That’s not always the case, e.g., older JDBC drivers might not support a method required by newer versions of the datasource class, especially for more obscure databases such as hive.

(Note: I don’t mean to pick on Hikari here. I’m seeing this problem in several libraries and I’m just using it as an example.)

The test should be straightforward. With one test class per datasource version:

ClassLoader oldClassLoader = Thread.currentThread().getContextClassLoader();
for (Artifact artifact : /* Aether query */) {
    try {
        URL[] urls = new URL[] {
            new URL("file", "", artifact.getFile());
        }
        ClassLoader cl = new URLClassLoader(urls, oldClassLoader);
        Thread.currentThread().setContextClassLoader(cl);

        HikariConfig config = new HikariConfig();
        config.setJdbcUrl(TEST_URL);
        config.setDriverClassName(DRIVER_CLASSNAME);
        DataSource ds = new HikariDataSource(config);
        try (Connection conn = ds.getConnection();
                Statement stmt = conn.createStatement();
                ResultSet rs = stmt.executeQuery("select 1 as x")) {
            assertThat(rs.next(), equalTo(true));
            assertThat(rs.getInt("x"), equalTo(1);
        }
    } finally {
        Thread.currentThread().setContextClassLoader(oldClassLoader);
    }
}

(Note: I’m actually using a parameterized junit test that uses the loop to produce the list of parameters. Each parameterized test is then run individually. I’m using an explicit loop here to emphasize the need to restore the environment after each test.)

Only one problem – it can’t find the driver class. Looking at the source code in github reveals the problem:

public void setDriverClassName(String driverClassName) {
    Class c = HikariConfig.class.getClassLoader().loadClass(driverClassName);
    ...
}

The Hikari classes were loaded by a different classloader than the JDBC driver classes and the ‘parent’ relationship between the classloaders goes the wrong way.

The fix isn’t hard – I need to modify my classloader so it loads both the Hikari datasource library and the JDBC driver library. This requires the use of reflection to create and configure the HikariConfig and HikariDataSource classes but that’s not too hard if I use commons-lang3 helper classes. There’s even a benefit to this approach – I can specify both datasource and JDBC driver jars in the test parameters and no longer need a separate test class for each version of the datasource.

Unfortunately it doesn’t work. I haven’t dug deeper into the class but I noticed the setter only verifies that the class is visible. It’s actually loaded and used elsewhere and it might use a different classloader at that point. Research continues….

But wait, it gets worse!

As an alternative I tried to explicitly register the JDBC driver in order to create the datasource without explicitly naming the JDBC driver classname (if possible):

ClassLoader oldClassLoader = Thread.currentThread().getContextClassLoader();
Driver driver = null;
for (Artifact artifact : /* Aether query */) {
    try {
        URL[] urls = new URL[] {
            new URL("file", "", artifact.getFile());
        }
        ClassLoader cl = new URLClassLoader(urls, oldClassLoader);
        Thread.currentThread().setContextClassLoader(cl);

        Class driverClass = (Class) cl.loadClass(DRIVER_NAME);
        driver = driverClass.newInstance();
        DriverManager.registerDriver(driver);

        ...

    } finally {
        if (driver != null) {
            DriverManager.deregisterDriver(driver);
        }
        Thread.currentThread().setContextClassLoader(oldClassLoader);
    }
}

Incredibly this fails – the deregisterDriver() call throws a SecurityException! This happens even when I explicitly set a permissive SecurityManager in the test setup. Digging into the code I discovered that the DriverManager checks whether the caller has the ability to load the class being deregistered. That sounds like a basic sanity check against malicious behavior but it introduces a classloader dependency. Again it’s not using the classloader I created in order to isolate my tests. The DriverManager is a core class so there’s no solution to this problem.

Edited to add…

I meant that there’s no clean solution to this problem. The DriverManager class uses reflection to learn the classloader of the calling method and verifies that the driver is accessible to it. In our case it’s not – we created a new classloader and it’s still our thread’s contextClassLoader but we’re calling the deregisterDriver() method from a class loaded by the original classloader.

One solution is to write and maintain another class that exists solely to deregister the driver class. That is non-obvious and will be a pain to maintain.

The other solution is to use reflection to make the internal registeredDrivers collection accessible and directly manipulate it in our ‘finally’ clause. That was my final solution.

Lessons learned

If we’re writing a library that allows the user to specify a classname at runtime we MUST test the scenario where the user loads the containing jar in a separate classloader. It’s not enough to only test it when containing jar is in the same classpath as our library – the jar might ultimately be provided by the end user and not the developer.

I’m cleaning up some tests at my new job and came across an interesting difference in opinion. Here are two ways to write a test. Which is better?

Context: the class being tested acts as a translation layer between our internal abstraction layer and a traditional JDBC driver. JPA and other ORM frameworks are not a viable option since we must work with arbitrary databases. We usually don’t want to call verify() since we want to test behavior, not implementation, but in this case the behavior we want to test is whether the appropriate calls are made to the mocked JDBC objects.

(Implementation note: we are using easymock but we can create similar code in jmock and mockito.)

Approach 1

final Connection conn = createMock(Connection.class);
final PreparedStatement stmt = createMock(PreparedStatement.class);

// more initialization

expect(conn.prepareStatement("insert into foo(a, b, c) values (?, ?, ?)")).andReturn(stmt);
stmt.setString(1, "Larry");
expectLastCall();
stmt.setString(2, "Curly");
expectLastCall();
stmt.setString(3, "Moe");
expectLastCall();
expect(stmt.execute()).andReturn(true);

// more initialization

replay(conn, stmt);

// run code under test

verify(conn, stmt);
}

Approach 2

final Connection conn = createMock(Connection.class);
final PreparedStatement stmt = createMock(PreparedStatement.class);

final String expectedSql = "insert into foo(a, b, c) values (?, ?, ?)";
final List<String> expectedValues = ImmutableList.of("Larry", "Curly", "Moe");

final Capture<String> actualSql = newCapture();
final Capture<String> actualValues = newCapture(CaptureType.ALL);

// more initialization

expect(conn.prepareStatement(capture(actualSql))).andReturn(stmt);
for (int i = 0; i < expectedValues.size(); i++) {
    stmt.setString(eq(i + 1), actualValues);
    expectLastCall();
}
expect(stmt.execute()).andReturn(true);

// more initialization

replay(conn, stmt);

// run code under test

assertEquals(expectedSql, actualSql);
assertEquals(expectedValues, actualValues);

verify(conn, stmt);
}

Both tests will fail if the expected SQL or values are different than expected. The former creates a framework exception (unexpected method call/missing method call), the latter creates a standard JUnit failure giving expected and actual values.

My coworker argues that the first approach is better since it’s more concise. That’s a good point – shorter methods are easier to understand and maintain.

I argue that the second approach is better since the messages are a lot clearer and the code is much more explicit that we’re concerned about the arguments to the mocked methods. The second approach will also be a lot easier to convert to a parameterized test in the future. Furthermore the actual code (not the snippet above) often uses the expectedValues value as an argument to the code under test. This reduces the risk of breaking tests because we updated one value but not the corresponding value.

Given-When-Then

Academic programs rarely spend much time on testing methodologies and many companies still treat testing as grunt work for the junior people instead of something critical to the long-term success of the project. We would never think it’s enough to just sit down and bang out code but we’ll do exactly that with test code.

No, we need to think about what we’re trying to accomplish and the best way to do it. Fortunately some very smart people have been thinking about this for a long time. One approach is Given-When-Then. Some test frameworks are explicitly built around this approach. JUnit is not but it’s easy to follow as a heuristic.

The second approach is easy to convert to Given-When-Then.

Given-When-Then Approach

Capture<String> setupForPreparedStatement(Connection conn, PreparedStatement stmt, Capture<Object> actualValues)
        throws SQLException {
    final Capture<String> actualSql = newCapture();

    expect(conn.prepareStatement(capture(actualSql))).andReturn(stmt);
    for (int i = 0; i < expectedValues.size(); i++) {
        Object obj = expectedValues.get(i);
        if (obj == null) {
            stmt.setNull(eq(i + 1), anyInt());
        } else if (obj instanceof String) {
            stmt.setString(eq(i + 1), (String) actualValues);
        } else if (obj instanceof BigDecimal) {
            stmt.setBigDecimal(eq(i + 1), (BigDecimal) actualValues);
        } else ... {
        }
        expectLastCall();
    }
    expect(stmt.execute()).andReturn(true);

    return actualSql;
}

public void test1() throws SQLException {
given:
    final Connection conn = createMock(Connection.class);
    final PreparedStatement stmt = createMock(PreparedStatement.class);
    final Capture<String> actualValues = newCapture(CaptureType.ALL);

    setupForPreparedStatement(conn, stmt, actualValues);

when:
    final List<Object> expectedValues = ImmutableList. of("Larry", "Curly", "Moe"); 

then:
    replay(conn, stmt);
    // run code under test
    verify(conn, stmt);

    assertEquals(expectedValues, actualValues);
}

(For clarity I’ve removed the test for the expected SQL statement.)

In this code there is absolutely nothing in the setup that makes assumptions about what values will be passed to the mocked objects. It doesn’t even make assumptions about what SQL commands will be passed, just that we want to create a prepared statement, populate it, then execute it.

It’s not hard to take this a step further and decree that all ‘expect’ calls should be done in setup methods and maintained by the developer working on the tested class. The actual test methods will be maintained by other people and follow the “test behavior, not implementation” rule.

If we don’t need to verify() the mocked objects – and remember we usually won’t since we want to test behavior and not implementation – then we can make the test even more concise.

Given-When-Then Approach without verify()

Capture<String> setupForPreparedStatement(Capture<Object> actualValues) throws SQLException {
    final Connection conn = createMock(Connection.class);
    final PreparedStatement stmt = createMock(PreparedStatement.class);
    final Capture<String> actualSql = newCapture();

    expect(conn.prepareStatement(capture(actualSql))).andReturn(stmt);
    for (int i = 0; i < expectedValues.size(); i++) {
        Object obj = expectedValues.get(i);
        if (obj == null) {
            stmt.setNull(eq(i + 1), anyInt());
        } else if (obj instanceof String) {
            stmt.setString(eq(i + 1), (String) actualValues);
        } else if (obj instanceof BigDecimal) {
            stmt.setBigDecimal(eq(i + 1), (BigDecimal) actualValues);
        } else ... {
        }
        expectLastCall();
    }
    expect(stmt.execute()).andReturn(true);
    replay(conn, stmt);

    return actualSql;
}

public void test1() throws SQLException {
given:
    final Capture<String> actualValues = newCapture(CaptureType.ALL);
    setupForPreparedStatement(actualValues);

when:
    final List<Object> expectedValues = ImmutableList. of("Larry", "Curly", "Moe"); 

then:
    // run code under test

    assertEquals(expectedValues, actualValues);
}

We have written many thousands of JUnit3 tests over the last decade and are now trying to consolidate the results in a database instead of scattered log files. It turns out to be remarkably easy to extend the TestCase class to do this. Note: this approach does not directly apply to JUnit4 or other test frameworks but it’s usually possible to do something analogous.

The tested class and its test

For demonstration purposes we can define a class with a single method to test.

public class MyTestedClass {

    public String op(String a, String b) {
        return ((a == null) ? "" : a) + ":" + ((b == null) ? "" : b);
    }
}

A class with a single method to be tested is less of a restriction than you might think. We are only testing four methods in the thousands of tests I mentioned earlier.

Here are a handful of tests for the class above.

public class MySimpleTest extends SimpleTestCase {

    private MyTestedClass obj = new MyTestedClass();

    public void test1() {
        assertEquals("a:b", obj.op("a", "b"));
    }

    public void test2() {
        assertEquals(":b", obj.op(null, "b"));
    }

    public void test3() {
        assertEquals("a:", obj.op("a", null));
    }

    public void test4() {
        assertEquals(":", obj.op(null, null));
    }

    public void test5() {
        // this will fail
        assertEquals(" : ", obj.op(null, null));
    }
}

Capturing basic information with a TestListener

JUnit3 allows listeners to be added their test processes. This listener is called before and after the test is run, plus anytime a test fails or has an error (throws an exception). This TestListener writes basic test information to System.out as a proof of concept. It would be easy to modify it to write the information to a database, a JMS topic, etc.

public class SimpleTestListener implements TestListener {
    private static final TimeZone UTC = TimeZone.getTimeZone("UTC");
    private long start;
    private boolean successful = true;
    private String name;
    private String failure = null;

    SimpleTestListener() {
    }

    public void setName(String name) {
        this.name = name;
    }

    public void startTest(Test test) {
        start = System.currentTimeMillis();
    }

    public void addError(Test test, Throwable t) {
        // cache information about error.
        successful = false;
    }

    public void addFailure(Test test, AssertionFailedError e) {
        // cache information about failure.
        failure = e.getMessage();
        successful = false;
    }

    /**
     * After the test finishes we can update the database with statistics about
     * the test - name, elapsed time, whether it was successful, etc.
     */
    public void endTest(Test test) {
        long elapsed = System.currentTimeMillis() - start;

        SimpleDateFormat fmt = new SimpleDateFormat();
        fmt.setTimeZone(UTC);

        System.out.printf("[%s, %s, %s, %d, %s, %s]\n", test.getClass().getName(), name, fmt.format(new Date(start)),
                elapsed, failure, Boolean.toString(successful));

        // write any information about errors or failures to database.
    }
}

A production TestListener should do a lot more with errors and failures. I’ve skipped that in order to focus on the broader issues.

This listener is not thread-safe so we will want to use a Factory pattern to create a fresh instance for each test. We can create heavyweight objects in the factory, e.g., open a SQL DataSource in the factory and pass a fresh Connection to each instance.

public class SimpleTestListenerFactory {
    public static final SimpleTestListenerFactory INSTANCE = new SimpleTestListenerFactory();

    public SimpleTestListenerFactory() {
        // establish connection data source here?
    }

    public SimpleTestListener newInstance() {
        // initialize listener.
        SimpleTestListener listener = new SimpleTestListener();
        return listener;
    }
}

If we know the test framework is purely serial we can capture all console output by creating a buffer and calling System.setOut() in startTest() and then restoring the original System.out in endTest(). This works well as long as tests never overlap but will cause problems otherwise. This can be problematic though – IDEs may have their own test runners that allow concurrent execution.

We override the standard run() method with our own that creates and registers a listener before calling the existing run() method.

public class SimpleTestCase extends TestCase {

    public void run(TestResult result) {
        SimpleTestListener l = SimpleTestListenerFactory.INSTANCE.newInstance();
        result.addListener(l);
        l.setName(getName());
        super.run(result);
        result.removeListener(l);
    }
}

We now get the expected results to System.out.

[MySimpleTest, test1, 8/2/15 11:58 PM, 0, null, true]
[MySimpleTest, test2, 8/2/15 11:58 PM, 10, null, true]
[MySimpleTest, test3, 8/2/15 11:58 PM, 0, null, true]
[MySimpleTest, test4, 8/2/15 11:58 PM, 0, null, true]
[MySimpleTest, test5, 8/2/15 11:58 PM, 4, expected same:<:> was not:< : >, false]

Capturing call information with a facade and TestListener

This is a good start but we might be able to do better. Only 4 methods are called in the thousands of tests mentioned above – it would be extremely powerful if we could capture the input and output values on those calls.

It is easy to wrap these functions with AOP, or a logging facade if AOP is not acceptable for some reason. In simple cases we can simply capture the input and output values.

public class MyFacadeClass extends MyTestedClass {
    private MyTestedClass parent;
    private String a;
    private String b;
    private String result;

    public MyFacadeClass(MyTestedClass parent) {
        this.parent = parent;
    }

    public String getA() {
        return a;
    }

    public String getB() {
        return b;
    }

    public String getResult() {
        return result;
    }

    /**
     * Wrap tested method so we can capture input and output.
     */
    public String op(String a, String b) {
        this.a = a;
        this.b = b;
        String result = parent.op(a, b);
        this.result = result;
        return result;
    }
}

We log the basic information as before and add just a bit new code to log the inputs and outputs.

public class AdvancedTestListener extends SimpleTestListener {

    AdvancedTestListener() {
    }

    /**
     * Log information as before but also log call details.
     */
    public void endTest(Test test) {
        super.endTest(test);

        // add captured inputs and outputs
        if (test instanceof MyAdvancedTest) {
            MyTestedClass obj = ((MyAdvancedTest) test).obj;
            if (obj instanceof MyFacadeClass) {
                MyFacadeClass facade = (MyFacadeClass) obj;
                System.out.printf("[, , %s, %s, %s]\n", facade.getA(), facade.getB(), facade.getResult());
            }
        }
    }
}

The logs now show both the basic information and the call details.

[MyAdvancedTest, test2, 8/3/15 12:13 AM, 33, null, true]
[, , null, b, :b]
[MyAdvancedTest, test3, 8/3/15 12:13 AM, 0, null, true]
[, , a, null, a:]
[MyAdvancedTest, test4, 8/3/15 12:13 AM, 0, null, true]
[, , null, null, :]
[MyAdvancedTest, test1, 8/3/15 12:13 AM, 0, null, true]
[, , a, b, a:b]

We want to associate the basic and call details but that’s easily handled by adding a unique test id.

This approach is not enough in the real world where the tested methods may be called multiple times during a single test. In this case we need to either have a way to cache multiple sets of input and output values or to extend the listener so we can call it at the end of each covered method.

We can make our results more extensible by encoding the results in XML or JSON instead of a simple list. This will allow us to only capture values of interest or to easily handle fields added in the future.

[MyAdvancedTest, test2, 8/3/15 12:13 AM, 33, null, true]
{"a":null, "b":"b", "results":":b" }
[MyAdvancedTest, test3, 8/3/15 12:13 AM, 0, null, true]
{"a":"a", "b":null, "results":"a:" }
[MyAdvancedTest, test4, 8/3/15 12:13 AM, 0, null, true]
{"a":null, "b":null, "results":":" }
[MyAdvancedTest, test1, 8/3/15 12:13 AM, 0, null, true]
{"a":" a", "b":"b", "results":" a:b" }

Capturing assertX information

We can now rerun the tests by replaying the captured inputs but there are two problems with blindly comparing the results. First, it will be a lot of unnecessary work if we only care about a single value. Second, many tests are non-deterministic (e.g., they use canned data that changes over time or even live data) and things we don’t care about may change.

This is not an easy problem. If we’re lucky the tests will follow the standard pattern and we can make a good guess at what tests are being performed but it needs to be manually verified.

First, we need to wrap the tested method’s results with a facade that captures some or all method calls. The call history should become available in a form that we can replay later, e.g., a sequence of method names and serialized parameters.

Second, we need to wrap the TestCase assertX methods so that we capture the recent method calls and the values passed to the assert call (plus the results, of course).

Example

The process is easiest to show – and demolish – with an example. Let’s start with a simple POJO.

public class Person {
    private String firstName;
    private String lastName;

    public String getFirstName() { return firstName; }
    public String getLastName() { return lastName; }
}

In this case our facade only needs to record the method name.

A typical test method is

public void test1() {
    Person p = getTestPerson();
    assertEquals("John", p.getFirstName());
    assertEquals("Smith", p.getLastName());
}

with a wrapped assertX method of

static PersonFacade person;

public static void assertEquals(String expected, String actual) {
    // ignoring null handling...
    boolean results = expected.equals(actual);
    LOG.log("assertEquals('" + expected + "',"+person.getMethodsCalled()+ ") = " + results);
    person.clearMethodsCalled();
    if (!results) {
        throw new AssertionFailedError("Expected same:<" + expected + " > was not:<" + actual + ">");
    }
}

so we would get results like

assertEquals('John', getFirstName()) = true;
assertEquals('Smith', getLastName()) = false;

It’s not hard to see how this could be parsed by a test framework but it’s too early to celebrate. The second test method is

public void test1() {
    Person p = getTestPerson();
    assertEquals("john", p.getFirstName().toLowerCase());
}

and our simple code will not capture the toLowerCase(). Our log will wrongly record

assertEquals('John', getFirstName()) = false;

A more pathological case is

public void test1() {
    Person p = getTestPerson();
    LOG.log("testing " + p.getFirstName());
    assertEquals("john", "joe");
}

where the assertion has nothing to do with the wrapped class.

There are obvious bandaids, e.g., we could capture the return values in our facade, but this is a very deep rabbit hole that we want to stay far away from. I think the answer is to make a reasonable first attempt, manually verify the results, and leave it at that. (Alternative: rewrite the tests to a form that can be captured.)

In 2011 I wrote a series of articles on PostgreSQL PL/Java. The basic information is still solid but there is a now a much easier way to install PL/Java from source. This also eliminates the need to depend on third parties to create packages. These notes will be fairly brief since I assume my readers are already familiar with git and maven.

(Note: I’ve passed this information to the PL/Java team so it may already be handled by the time you read this.)

Perform the basic build

1. Clone the PL/Java repository at https://github.com/tada/pljava.
2. Run maven not make.
3. …
4. Profit!

Of course it’s not that simple. Maven can pull in its own dependencies but we still need several specialized libraries beyond the standard GNU toolchain. On my Ubuntu system I needed:

• postgresql-server-dev-9.4
• libpg-dev
• libpgtypes3
• libecpg-dev

(I don’t know the corresponding package names for RedHat/Fedora/CentOS.)

It may take a bit of experimentation but it shouldn’t be too hard to identify all of the packages you need. Just remember that you’ll usually want the packages with the “-dev” extension.

There are a large number of compiler warnings and errors but most if not all seem to be related to sign conversions. This warrants further investigation – sign conversion warnings indicate possible attack surfaces by malicious users – but for now we should be fine as long as maven succeeds. We need three files:

./src/sql/install.sql
./pljava/target/pljava-0.0.2-SNAPSHOT.jar
./pljava-so/target/nar/pljava-so-0.0.2-SNAPSHOT-i386-Linux-gpp-shared/lib/i386-Linux-gpp/shared/libpljava-so-0.0.2-SNAPSHOT.so

Copying the files

We can now copy the three files to their respective locations.

$ sudo cp ./pljava-so/target/nar/pljava-so-0.0.2-SNAPSHOT-i386-Linux-gpp-shared/lib/i386-Linux-gpp/shared/libpljava-so-0.0.2-SNAPSHOT.so \
  /usr/lib/postgresql/9.4/lib/pljava.so

$ sudo cp ./pljava/target/pljava-0.0.2-SNAPSHOT.jar /usr/share/postgresql/9.4/extension/pljava--1.4.4.jar

$ sudo cp ./src/sql/install.sql /usr/share/postgresql/9.4/extension/pljava--1.4.4.sql

We can learn the correct target directory with the ‘pg_config’ command.

$ pg_config
PKGLIBDIR = /usr/lib/postgresql/9.4/lib
SHAREDIR = /usr/share/postgresql/9.4
...

I have changed the version from 0.0.2-SNAPSHOT to 1.4.4 since we want to capture the PL/Java version, not the pom.xml version. I hope these will soon be kept in sync.

Editing pljava–1.4.4.sql

We need to add two lines to the installation sql:

SET PLJAVA.CLASSPATH='/usr/share/postgresql/9.4/extension/pljava--1.4.4.jar';
SET PLJAVA.VMOPTIONS='-Xms64M -Xmx128M';

It’s important to remember that there is a unique JVM instantiated for each database connection. Memory consumption can become a major concern when you have 20+ simultaneous connections.

Create the pljava.control file

We must tell PostgreSQL about the new extension. This is handled by a control file.

/usr/share/postgresql/9.4/extension/pljava.control

# pljava extension
comment = 'PL/Java bundled as an extension'
default_version = '1.4.4'
relocatable = false

Make libjvm.so visible

We normally specify the location of the java binaries and shared libraries via the JAVA_HOME environment variable. This isn’t an option with the database server.

There are two approaches depending on whether you want to make the java shared library (libjvm.so) visible to all applications or just the database server. I think the former is easiest.

We need to create a single file

/etc/ld.so.conf.d/i386-linux-java.conf

/usr/lib/jvm/java-8-openjdk-i386/jre/lib/i386/server

where most of the pathname comes from JAVA_HOME. The location may be different on your system. The directory must contain the shared library ‘libjvm.so’.

We must also tell the system to refresh its cache.

$ sudo ldconfig
$ sudo ldconfig -p | grep jvm
	libjvm.so (libc6) => /usr/lib/jvm/java-8-openjdk-i386/jre/lib/i386/server/libjvm.so
	libjsig.so (libc6) => /usr/lib/jvm/java-8-openjdk-i386/jre/lib/i386/server/libjsig.so

Loading the extension

We can now easily load and unload PL/Java.

=> CREATE EXTENSION pljava;
CREATE EXTENSION

=> DROP EXTENSION pljava;
DROP EXTENSION

In case of flakiness…

If the system seems flaky you can move the two ‘set’ commands into the postgresql.conf file.

/etc/postgresql/9.4/main/postgresql.conf

#------------------------------------------------------------------------------
# CUSTOMIZED OPTIONS
#------------------------------------------------------------------------------

# Add settings for extensions here

PLJAVA.CLASSPATH='/usr/share/postgresql/9.4/extension/pljava--1.4.4.jar'
PLJAVA.VMOPTIONS='-Xms64M -Xmx128M'

A crazy idea came up during the post-mortem discussions in the Coursera security capstone project. Can a class encrypt itself during serialization?

This is mostly an academic “what if” exercise. It is hard to think of a situation where we would want to rely on an object self-encrypting instead of using an explicit encryption mechanism during persistence. I’ve only been able to identify one situation where we can’t simply make a class impossible to serialize:

HTTPSession passivation

Appservers may passivate inactive HTTPSessions to save space or to migrate a session from one server to another. This is why sessions should only contain Serializable objects. (This restriction is often ignored in small-scale applications that can fit on a single server but that can cause problems if the implementation needs to be scaled up or out.)

One approach (and the preferred approach?) is for the session to write itself to a database during passivation and reload itself during activation. The only information actually retained is what’s require to reload the data, typically just the user id. This adds a bit of complexity to the HTTPSession implementation but it has many benefits. One major benefit is that it trivial to ensure sensitive information is encrypted.

It’s not the only approach and some sites may prefer to use standard serialization. Some appservers may keep copies of serialized copies of “live” sessions in an embedded database like H2. A cautious developer may want to ensure that sensitive information is encrypted during serialization even if it should never happen.

Note: a strong argument can be made that the sensitive information shouldn’t be in the session in the first place – only retrieve it when necessary and safely discard it once it is no longer needed.

The approach

The approach I’m taking is based on the serialization chapter in Effective Java. In broad terms we want to use a serialization proxy to handle the actual encryption. The behavior is

The reason the protected class throws an exception when the deserialization methods are called is because it prevents attacks through attacker-generated serialized objects. See the discussion on the bogus byte-stream attack and internal field theft attack in the book mentioned above.

This approach has a big limitation – the class cannot be extended without the subclass reimplementing the proxy. I don’t think this is an issue in practice since this technique will only be used to protect classes containing sensitive information and it would rarely be desirable to add methods beyond the ones anticipated by the designers.

The proxy class handles encryption. The implementation below shows the use of a random salt (IV) and cryptographically strong message digest (HMAC) to detect tampering.

The code

public class ProtectedSecret implements Serializable {
    private static final long serialVersionUID = 1L;

    private final String secret;

    /**
     * Constructor.
     * 
     * @param secret
     */
    public ProtectedSecret(final String secret) {
        this.secret = secret;
    }

    /**
     * Accessor
     */
    public String getSecret() {
        return secret;
    }

    /**
     * Replace the object being serialized with a proxy.
     * 
     * @return
     */
    private Object writeReplace() {
        return new SimpleProtectedSecretProxy(this);
    }

    /**
     * Serialize object. We throw an exception since this method should never be
     * called - the standard serialization engine will serialize the proxy
     * returned by writeReplace(). Anyone calling this method directly is
     * probably up to no good.
     * 
     * @param stream
     * @return
     * @throws InvalidObjectException
     */
    private void writeObject(ObjectOutputStream stream) throws InvalidObjectException {
        throw new InvalidObjectException("Proxy required");
    }

    /**
     * Deserialize object. We throw an exception since this method should never
     * be called - the standard serialization engine will create serialized
     * proxies instead. Anyone calling this method directly is probably up to no
     * good and using a manually constructed serialized object.
     * 
     * @param stream
     * @return
     * @throws InvalidObjectException
     */
    private void readObject(ObjectInputStream stream) throws InvalidObjectException {
        throw new InvalidObjectException("Proxy required");
    }

    /**
     * Serializable proxy for our protected class. The encryption code is based
     * on https://gist.github.com/mping/3899247.
     */
    private static class SimpleProtectedSecretProxy implements Serializable {
        private static final long serialVersionUID = 1L;
        private String secret;

        private static final String CIPHER_ALGORITHM = "AES/CBC/PKCS5Padding";
        private static final String HMAC_ALGORITHM = "HmacSHA256";

        private static transient SecretKeySpec cipherKey;
        private static transient SecretKeySpec hmacKey;

        static {
            // these keys can be read from the environment, the filesystem, etc.
            final byte[] aes_key = "d2cb415e067c7b13".getBytes();
            final byte[] hmac_key = "d6cfaad283353507".getBytes();

            try {
                cipherKey = new SecretKeySpec(aes_key, "AES");
                hmacKey = new SecretKeySpec(hmac_key, HMAC_ALGORITHM);
            } catch (Exception e) {
                throw new ExceptionInInitializerError(e);
            }
        }

        /**
         * Constructor.
         * 
         * @param protectedSecret
         */
        SimpleProtectedSecretProxy(ProtectedSecret protectedSecret) {
            this.secret = protectedSecret.secret;
        }

        /**
         * Write encrypted object to serialization stream.
         * 
         * @param s
         * @throws IOException
         */
        private void writeObject(ObjectOutputStream s) throws IOException {
            s.defaultWriteObject();
            try {
                Cipher encrypt = Cipher.getInstance(CIPHER_ALGORITHM);
                encrypt.init(Cipher.ENCRYPT_MODE, cipherKey);
                byte[] ciphertext = encrypt.doFinal(secret.getBytes("UTF-8"));
                byte[] iv = encrypt.getIV();

                Mac mac = Mac.getInstance(HMAC_ALGORITHM);
                mac.init(hmacKey);
                mac.update(iv);
                byte[] hmac = mac.doFinal(ciphertext);

                // TBD: write algorithm id...
                s.writeInt(iv.length);
                s.write(iv);
                s.writeInt(ciphertext.length);
                s.write(ciphertext);
                s.writeInt(hmac.length);
                s.write(hmac);
            } catch (Exception e) {
                throw new InvalidObjectException("unable to encrypt value");
            }
        }

        /**
         * Read encrypted object from serialization stream.
         * 
         * @param s
         * @throws InvalidObjectException
         */
        private void readObject(ObjectInputStream s) throws ClassNotFoundException, IOException, InvalidObjectException {
            s.defaultReadObject();
            try {
                // TBD: read algorithm id...
                byte[] iv = new byte[s.readInt()];
                s.read(iv);
                byte[] ciphertext = new byte[s.readInt()];
                s.read(ciphertext);
                byte[] hmac = new byte[s.readInt()];
                s.read(hmac);

                // verify HMAC
                Mac mac = Mac.getInstance(HMAC_ALGORITHM);
                mac.init(hmacKey);
                mac.update(iv);
                byte[] signature = mac.doFinal(ciphertext);

                // verify HMAC
                if (!Arrays.equals(hmac, signature)) {
                    throw new InvalidObjectException("unable to decrypt value");
                }

                // decrypt data
                Cipher decrypt = Cipher.getInstance(CIPHER_ALGORITHM);
                decrypt.init(Cipher.DECRYPT_MODE, cipherKey, new IvParameterSpec(iv));
                byte[] data = decrypt.doFinal(ciphertext);
                secret = new String(data, "UTF-8");
            } catch (Exception e) {
                throw new InvalidObjectException("unable to decrypt value");
            }
        }

        /**
         * Return protected object.
         * 
         * @return
         */
        private Object readResolve() {
            return new ProtectedSecret(secret);
        }
    }
}

It should go without saying that the encryption keys should not be hard-coded or possibly even cached as shown. This was a short-cut to allow us to focus on the details of the implementation.

Different keys should be used for the cipher and message digest. You will seriously compromise the security of your system if the same key is used.

Two other things should be handled in any production system: key rotation and changing the cipher and digest algorithms. The former can be handled by adding a ‘key id’ to the payload, the latter can be handled by tying the serialization version number and cipher algorithms. E.g., version 1 uses standard AES, version 2 uses AES-256. The deserializer should be able to handle old encryption keys and ciphers (within reason).

Test code

The test code is straightforward. It creates an object, serializes it, deserializes it, and compares the results to the original value.

public class ProtectedSecretTest {

    /**
     * Test 'happy path'.
     */
    @Test
    public void testCipher() throws IOException, ClassNotFoundException {
        ProtectedSecret secret1 = new ProtectedSecret("password");
        ProtectedSecret secret2;
        byte[] ser;

        // serialize object
        try (ByteArrayOutputStream baos = new ByteArrayOutputStream();
                ObjectOutput output = new ObjectOutputStream(baos)) {
            output.writeObject(secret1);
            output.flush();

            ser = baos.toByteArray();
        }

        // deserialize object.
        try (ByteArrayInputStream bais = new ByteArrayInputStream(ser); ObjectInput input = new ObjectInputStream(bais)) {
            secret2 = (ProtectedSecret) input.readObject();
        }

        // compare values.
        assertEquals(secret1.getSecret(), secret2.getSecret());
    }

    /**
     * Test deserialization after a single bit is flipped.
     */
    @Test(expected = InvalidObjectException.class)
    public void testCipherAltered() throws IOException, ClassNotFoundException {
        ProtectedSecret secret1 = new ProtectedSecret("password");
        ProtectedSecret secret2;
        byte[] ser;

        // serialize object
        try (ByteArrayOutputStream baos = new ByteArrayOutputStream();
                ObjectOutput output = new ObjectOutputStream(baos)) {
            output.writeObject(secret1);
            output.flush();

            ser = baos.toByteArray();
        }
        
        // corrupt ciphertext
        ser[ser.length - 16 - 1 - 3] ^= 1;

        // deserialize object.
        try (ByteArrayInputStream bais = new ByteArrayInputStream(ser); ObjectInput input = new ObjectInputStream(bais)) {
            secret2 = (ProtectedSecret) input.readObject();
        }

        // compare values.
        assertEquals(secret1.getSecret(), secret2.getSecret());
    }
}

Final words

I cannot overemphasize this – this is primarily an intellectual exercise. As usual the biggest problem is key management, not cryptography, and with the level of effort required for the former you can probably implement a more traditional solution more quickly.

This may still be “good enough” in some situations. For instance you may only need to keep the data around during the duration of a long-running application. In this case you can create random keys at startup and simply discard all serialized data after the program ends.

Source code: https://gist.github.com/beargiles/90182af6f332830a2e0e

It’s amazing how I can have a huge pile of books to read and then another load is dumped on top of them. le sigh. I still have 3-4 technical blog entries in various stages of completion on top of a dozen books for “professional development” at work.

The current top of the stack is cloud computing, specifically AWS. It turns out that there are several certifications available for AWS: https://aws.amazon.com/certification/. The program is still undergoing growth pains, e.g., the nearest testing site to metro Denver appears to be in Winnemucca, Nevada, or maybe some hayseed college in Kansas. The Kryterion testing sites are probably added as people request them as opposed to running down a list of the top N technical markets. (Do you think the startups in Boulder aren’t heavy users of the cloud?)

Anyway I’ve mentioned before how I like to use certification objectives as study guides even if I don’t actually take the exam. I found a few resources on udemy.com that should go a long way. I was already familiar with most (not all) of the information on EC2 and S3 but was pleasantly surprised to learn about the other services.

Udemy Courses

• Amazon Web Services for Entrepreneurs and Bloggers (free) – good introduction. Plan on 6 hours.
• Amazon Web Services Certified Solution Architect – Associate Level (2014) ($59) – I haven’t taken this yet but it’s probably also a good overview. Plan on 10 hours.
• Amazon Web Services – Web Hosting & Cloud Computing with AWS ($49) – highly recommended, much more detailed than first course. Plan on 12+ hours.
• Amazon Web Services Certified Developer – Associate Level ($199) – in-depth discussion of using the AWS API. Plan on 10 hours plus many hours playing around with the SKD in your favorite language(s).

These courses are free under my corporate account so you should check with your employer first. If not Udemy regularly offers specials that can dramatically cut the cost of their courses.

How do you learn what cryptographic algorithms are available to you? The Java spec names several required ciphers, digests, etc., but a provider often offers more than that.

Fortunately this is easy to learn what’s available on our system.

public class ListAlgorithms {
    public static void main(String[] args) {
        // Security.addProvider(new
        // org.bouncycastle.jce.provider.BouncyCastleProvider());

        // get a list of services and their respective providers.
        final Map<String, List<Provider>> services = new TreeMap<>();

        for (Provider provider : Security.getProviders()) {
            for (Provider.Service service : provider.getServices()) {
                if (services.containsKey(service.getType())) {
                    final List<Provider> providers = services.get(service
                            .getType());
                    if (!providers.contains(provider)) {
                        providers.add(provider);
                    }
                } else {
                    final List<Provider> providers = new ArrayList<>();
                    providers.add(provider);
                    services.put(service.getType(), providers);
                }
            }
        }

        // now get a list of algorithms and their respective providers
        for (String type : services.keySet()) {
            final Map<String, List<Provider>> algs = new TreeMap<>();
            for (Provider provider : Security.getProviders()) {
                for (Provider.Service service : provider.getServices()) {
                    if (service.getType().equals(type)) {
                        final String algorithm = service.getAlgorithm();
                        if (algs.containsKey(algorithm)) {
                            final List<Provider> providers = algs
                                    .get(algorithm);
                            if (!providers.contains(provider)) {
                                providers.add(provider);
                            }
                        } else {
                            final List<Provider> providers = new ArrayList<>();
                            providers.add(provider);
                            algs.put(algorithm, providers);
                        }
                    }
                }
            }

            // write the results to standard out.
            System.out.printf("%20s : %s\n", "", type);
            for (String algorithm : algs.keySet()) {
                System.out.printf("%-20s : %s\n", algorithm,
                        Arrays.toString(algs.get(algorithm).toArray()));
            }
            System.out.println();
        }
    }
}

The system administrator can override the standard crypto libraries. In practice it’s safest to always load your own crypto library and either register it manually, as above, or better yet pass it as an optional parameter when creating new objects.

Algorithms

There are a few dozen standard algorithms. The ones we’re most likely to be interested in are:

Symmetric Cipher

• KeyGenerator – creates symmetric key
• SecretKeyFactor – converts between symmetric keys and raw bytes
• Cipher – encryption cipher
• AlgorithmParameters – algorithm parameters
• AlgorithmParameterGernerator – algorithm parameters

Asymmetric Cipher

• KeyPairGenerator – creates public/private keys
• KeyFactor – converts between keypairs and raw bytes
• Cipher – encryption cipher
• Signature – digital signatures
• AlgorithmParameters – algorithm parameters
• AlgorithmParameterGernerator – algorithm parameters

Digests

• MessageDigest – digest (MD5, SHA1, etc.)
• Mac – HMAC. Like a message digest but requires an encryption key as well so it can’t be forged by attacker

Certificates and KeyStores

• KeyStore – JKS, PKCS, etc.
• CertStore – like keystore but only stores certs.
• CertificateFactory – converts between digital certificates and raw bytes.

It is critical to remember that most algorithms are provided for backward compatibility and should not be used for in greenfield development. As I write this the generally accepted advice is:

• Use a variant of AES. Only use AES-ECB if you know with absolute certainty that you will never encrypt more than one blocksize (16 bytes) of data.
• Always use a good random IV even if you’re using AES-CBC. Do not use the same IV or an easily predicted one.
• Do not use less than 2048 bits in an asymmetric key.
• Use SHA-256 or better. MD-5 is considered broken, SHA-1 will be considered broken in the near future.
• Use PBKDF2WithHmacSHA1 to create AES key from passwords/passphrases. (See also Creating Password-Based Encryption Keys.)

Some people might want to use one of the other AES-candidate ciphers (e.g., twofish). These ciphers are probably safe but you might run into problems if you’re sharing files with other parties since they’re not in the required cipher suite.

Beware US Export Restrictions

Finally it’s important to remember that the standard Java distribution is crippled due to US export restrictions. You can get full functionality by installing a standard US-only file on your system but it’s hard if not impossible for developers to verify this has been done. In practice many if not most people use a third-party cryptographic library like BouncyCastle. Many inexperienced developers forget about this and unintentionally use crippled functionality.

An artist does not just draw an ear on the first try. He or she will do a study drawing different ears, ears from different angles, etc., until he understands it.

Likewise a software developer should not write new code just once. He or she should play around with it a bit until he truly understands it. Few things are more scary than a magic configuration file that “works” but nobody understands. To me it’s a classic “pay me now or pay me later” situation – it’s better to invest the time to understand it when it’s convenient, not at 3 AM when the production server is down and your boss’s boss is screaming for answers.

Many of us expand these small studies into small projects as a way to self-document what we’ve learned. A small project in a github stash is often a better way to refresh your memory than a large pile of static documentation.

Two things happen over time: the small projects get larger and they get more diverse^*. At some point it’s natural to start asking how they hook up, e.g., you might know how to write a persistence layer, a business layer, and functional tests. How do you wire them to create small functional tests that pull values from the database, perform calculations, and put the results back into the database?

These integrated projects will slowly become more and more complex. At some point it dawns on you that you’re spending more time thinking about what to do than actually doing it. In other words you’re acting as a project manager. A bad project manager, but a project manager.

The answer is to go to the dark side.

Well, at least visit it and bring back souvenirs.

If we’re in an agile shop we already have good idea about what we need to do. It’s easy to get the necessary software – starter licenses for Atlassian products are only $10/year (self-hosted) or $10/month (hosted) (prices subject to change). On the Microsoft side you can get SharePoint for as little as $3/month. For one user’s perspective see http://abovethelaw.com/2014/07/why-sharepoint-is-the-most-underutilized-legal-tool-that-microsoft-has-to-offer/ – it makes upper managements fascination with that product more understandable.

Good tools are important but we still need to know how to use them. This is where study guides for the Project Management Professional (PMP) are useful. We don’t need most of the material but it gives us a good conceptual framework to understand how to manage our own small projects and to be most effective at work.

All of this takes time – in fact it’s why I’ve been light on blogging – but it’s necessary as our projects get more complex. It isn’t fun but it’s a necessary skill that many people will consider more important than mastering a fourth javascript framework.

In my case I have about seven active projects and meta-projects in JIRA. Several side projects, blog ideas, professional development ideas, even tracking the time I’m spending learning Spanish and preparing for a half-marathon this winter. All told I easily have a year’s worth of weekend projects jotted down and it’s a lot easier to prioritize them when a new idea occurs to me. This would have been impossible a few years ago when I just jotted down notes on index cards that lived in a pile on the corner of my desk.

^* I’ll discuss this further later but there’s a tension between being a specialist and being a generalist. Specialists tend to find it easier to land jobs in the short term but if they’re not careful they can hit career death tied to a dying technology. Generalists are more likely to be the unemployed “second choice” but they’re also more likely to have long careers. This may be changing as more companies look for “devops” or “full stack engineers”. Generalists should find it easy to knit different projects together and to see where they have gaps in their knowledge.

A common problem is to determine the prime factorization of a number. The brute force approach is trial division (Wikipedia, Khan Academy) but that requires a lot of wasted effort if multiple numbers must be factored.

One widely used solution is the Sieve of Eratosthenes (Wikipedia, Math World). It is easy to modify the Sieve of Eratosthenes to contain the largest prime factor of each composite number. This makes it extremely cheap to subsequently compute the prime factorization of numbers.

If we only care about primality we can either use a bitmap with the Sieve of Eratosthenes, or use the Sieve of Atkin).

(Sidenote: for clarity I’m leaving out the common optimizations that follow from the facts that a prime number is always “1 mod 2, n > 2” and “1 or 5 mod 6, n > 5”. This can substantially reduce the amount of memory required for a sieve.)

public enum SieveOfEratosthenes {
    SIEVE;
    
    private int[] sieve;

    private SieveOfEratosthenes() {
        // initialize with first million primes - 15485865
        // initialize with first 10k primes - 104729
        sieve = initialize(104729);
    }

    /**
     * Initialize the sieve.
     */
    private int[] initialize(int sieveSize) {
        long sqrt = Math.round(Math.ceil(Math.sqrt(sieveSize)));
        long actualSieveSize = (int) (sqrt * sqrt);

        // data is initialized to zero
        int[] sieve = new int[actualSieveSize];

        for (int x = 2; x < sqrt; x++) {
            if (sieve[x] == 0) {
                for (int y = 2 * x; y < actualSieveSize; y += x) {
                    sieve[y] = x;
                }
            }
        }

        return sieve;
    }

    /**
     * Is this a prime number?
     *
     * @FIXME handle n >= sieve.length!
     * 
     * @param n
     * @return true if prime
     * @throws IllegalArgumentException
     *             if negative number
     */
    public boolean isPrime(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("value must be non-zero");
        }

        boolean isPrime = sieve[n] == 0;

        return isPrime;
    }

    /**
     * Factorize a number
     *
     * @FIXME handle n >= sieve.length!
     * 
     * @param n
     * @return map of prime divisors (key) and exponent(value)
     * @throws IllegalArgumentException
     *             if negative number
     */
    private Map<Integer, Integer> factorize(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("value must be non-zero");
        }

        final Map<Integer, Integer> factors = new TreeMap<Integer, Integer>();

        for (int factor = sieve[n]; factor > 0; factor = sieve[n]) {
            if (factors.containsKey(factor)) {
                factors.put(factor, 1 + factors.get(factor));
            } else {
                factors.put(factor, 1);
            }

            n /= factor;
        }

        // must add final term
        if (factors.containsKey(n)) {
            factors.put(n, 1 + factors.get(n));
        } else {
            factors.put(n, 1);
        }

        return factors;
    }

    /**
     * Convert a factorization to a human-friendly string. The format is a
     * comma-delimited list where each element is either a prime number p (as
     * "p"), or the nth power of a prime number as "p^n".
     * 
     * @param factors
     *            factorization
     * @return string representation of factorization.
     * @throws IllegalArgumentException
     *             if negative number
     */
    public String toString(Map factors) {
        StringBuilder sb = new StringBuilder(20);

        for (Map.Entry entry : factors.entrySet()) {
            sb.append(", ");

            if (entry.getValue() == 1) {
                sb.append(String.valueOf(entry.getKey()));
            } else {
                sb.append(String.valueOf(entry.getKey()));
                sb.append("^");
                sb.append(String.valueOf(entry.getValue()));
            }
        }

        return sb.substring(2);
    }
}

This code has a major weakness – it will fail if the requested number is out of range. There is an easy fix – we can dynamically resize the sieve as required. We use a Lock to ensure multithreaded calls don’t get the sieve in an intermediate state. We need to be careful to avoid getting into a deadlock between the read and write locks.

    private final ReadWriteLock lock = new ReentrantReadWriteLock();

    /**
     * Initialize the sieve. This method is called when it is necessary to grow
     * the sieve.
     */
    private void reinitialize(int n) {
        try {
            lock.writeLock().lock();
            // allocate 50% more than required to minimize thrashing.
            initialize((3 * n) / 2);
        } finally {
            lock.writeLock().unlock();
        }
    }

    /**
     * Is this a prime number?
     * 
     * @param n
     * @return true if prime
     * @throws IllegalArgumentException
     *             if negative number
     */
    public boolean isPrime(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("value must be non-zero");
        }

        if (n > sieve.length) {
            reinitialize(n);
        }

        boolean isPrime = false;
        try {
            lock.readLock().lock();
            isPrime = sieve[n] == 0;
        } finally {
            lock.readLock().unlock();
        }

        return isPrime;
    }

    /**
     * Factorize a number
     * 
     * @param n
     * @return map of prime divisors (key) and exponent(value)
     * @throws IllegalArgumentException
     *             if negative number
     */
    private Map<Integer, Integer> factorize(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("value must be non-zero");
        }

        final Map<Integer, Integer> factors = new TreeMap<Integer, Integer>();

        try {
            if (n > sieve.length) {
                reinitialize(n);
            }

            lock.readLock().lock();
            for (int factor = sieve[n]; factor > 0; factor = sieve[n]) {
                if (factors.containsKey(factor)) {
                    factors.put(factor, 1 + factors.get(factor));
                } else {
                    factors.put(factor, 1);
                }

                n /= factor;
            }
        } finally {
            lock.readLock().unlock();
        }

        // must add final term
        if (factors.containsKey(n)) {
            factors.put(n, 1 + factors.get(n));
        } else {
            factors.put(n, 1);
        }

        return factors;
    }

Iterable<Integer> and foreach loops

In the real world it’s often easier to use a foreach loop (or explicit Iterator) than to probe a table item by item. Fortunately it’s easy to create an iterator that’s built on top of our self-growing sieve.

   /**
     * @see java.util.List#get(int)
     *
     * We can use a cache of the first few (1000? 10,000?) primes
     * for improved performance.
     *
     * @param n
     * @return nth prime (starting with 2)
     * @throws IllegalArgumentException
     *             if negative number
     */
    public Integer get(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("value must be non-zero");
        }

        Iterator<Integer> iter = iterator();
        for (int i = 0; i < n; i++) {
            iter.next();
        }

        return iter.next();
    }

    /**
     * @see java.util.List#indexOf(java.lang.Object)
     */
    public int indexOf(Integer n) {
        if (!isPrime(n)) {
            return -1;
        }

        int index = 0;
        for (int i : sieve) {
            if (i == n) {
                return index;
            }
            index++;
        }
        return -1;
    }
   /**
     * @see java.lang.Iterable#iterator()
     */
    public Iterator<Integer> iterator() {
        return new EratosthenesListIterator();
    }

    public ListIterator<Integer> listIterator() {
        return new EratosthenesListIterator();
    }

    /**
     * List iterator.
     *
     * @author Bear Giles <bgiles@coyotesong.com>
     */
    static class EratosthenesListIterator extends AbstractListIterator<Integer> {
        int offset = 2;

        /**
         * @see com.invariantproperties.projecteuler.AbstractListIterator#getNext()
         */
        @Override
        protected Integer getNext() {
            while (true) {
                offset++;
                if (SIEVE.isPrime(offset)) {
                    return offset;
                }
            }
 
            // we'll always find a value since we dynamically resize the sieve.
        }

        /**
         * @see com.invariantproperties.projecteuler.AbstractListIterator#getPrevious()
         */
        @Override
        protected Integer getPrevious() {
            while (offset > 0) {
                offset--;
                if (SIEVE.isPrime(offset)) {
                    return offset;
                }
            }

            // we only get here if something went horribly wrong
            throw new NoSuchElementException();
        }
    }
}

IMPORTANT: The code

for (int prime : SieveOfEratosthenes.SIEVE) { ... }

is essentially an infinite loop. It will only stop once the JVM exhausts the heap space when allocating a new sieve.

In practice this means that the maximum prime we can maintain in our sieve is around 1 GB. That requires 4 GB with 4-byte ints. If we only care about primality and use a common optimization that 4 GB can hold information on 64 GB values. For simplicity we can call this 9-to-10 digit numbers (base 10).

What if we put our sieve on a disk?

There is no reason why the sieve has to remain in memory. Our iterator can quietly load values from disk instead of an in-memory cache. A 4 TB disk, probably accessed in raw mode, would seem to bump the size of our sieve to 14-to-15 digit numbers (base 10). In fact it will be a bit less because we’ll have to double the size of our primitive types from int to long, and then probably to an even larger format.

More! More! More!

We can dramatically increase the effective size of our sieve by noting that we only have to compute sqrt(n) to initialize a sieve of n values. We can flip that and say that a fully populated sieve of n values can be used to populate another sieve of n² values. In this case we’ll want to only populate a band, not the full n² sieve. Our in-memory sieve can now cover values up to roughly 40 digit numbers (base 10), and the disk-based sieve jumps to as much as 60 digit numbers (base 10), minus the space require for the larger values.

There is no reason why this approach can’t be taken even further – use a small sieve to bootstrap a larger transient sieve and use it, in turn, to populate an even larger sieve.

But how long will this take?

Aye, there’s the rub. The cost to initialize a sieve of n values is O(n²). You can use various tweaks to reduce the constants but at the end of the day you’re visiting every node once (O(n)), and then visiting some rolling value proportional to n beyond each of those points. For what it’s worth this is a problem where keeping the CPU’s cache architecture could make a big difference.

In practical terms any recent system should be able to create a sieve containing the first million primes within a few seconds. Bump the sieve to the first billion primes and the time has probably leapt to a week, maybe a month if limited JVM heap space forces us to use the disk heavily. My gut instinct is that it will take a server farm months to years to populate a TB disk

Why bother?

For most of us the main takeaway is a demonstration of how to start a collection with a small seed, say a sieve with n = 1000, and transparently grow it as required. This is easy with prime numbers but it isn’t a huge stretch to imagine the same approach being used with, oh, RSS feeds. We’re used to thinking of Iterators as some boring aspect of Collections but in fact they give us a lot of flexibility when used as part of an Iterable.

There is also a practical reason for a large prime sieve – factoring large numbers. There are several good algorithms for factoring large numbers but they’re expensive – even “small” numbers may take months or years on a server farm. That’s why the first step is always doing trial division with “small” primes – something that may take a day by itself.

Source Code

The good news is that I have published the source code for this… and the bad news is it’s part of ongoing doodling when I’m doing Project Euler problems. (There are no solutions here – it’s entirely explorations of ideas inspired by the problems. So the code is a little rough and should not be used to decide whether or not to bring me in for an interview (unless you’re impressed): http://github.com/beargiles/projecteuler.