Insights into Software

Distributed version control

2010-04-01T15:14:00.009-05:00

Recently, Joel on Software published a blog entry discussing the advantages a distributed version control system [DVCS] has over a version control system [VCS] with its dependency on a central repository. The key point, Joel says, is that "with distributed version control, the distributed part is actually not the most interesting part," but "that these systems think in terms of changes, not in terms of versions." Joel doesn't get it.

There is no magic merge bullet going on here; Mercurial (which has a great name (see definition 4)) doesn't track every refactoring operation the developer performs. It doesn't know (or care) that the developer moved a function from file A to file B. Rather, just like any other VCS it simply tracks the changes to the individual files A and B. While it can and should know that stuff was removed from file A and that stuff was added to file B, it cannot and should not know whether what was removed from A was transferred over to B. So, what is it that really differentiates a DVCS from other VCS applications?

According to Joel's own Mercurial manual the developer should use the tool as follows:

check in often
branch to test new approaches (branch to spike)
synchronize branches quickly
propagate changes (push and pull) often
add new code into the VCS quickly

Now, here's the interesting thing. All of these are factors described as "best practices" for Software Configuration Management [SCM]. What a surprise.

It isn't (just) about whether or not the tool tracks changesets or file versions, it is about whether the tool facilitates best practices for SCM. It turns out that Mercurial does an outstanding job across the board:

it makes cloning (branching) incredibly fast and easy. This encourages developers to branch quickly and often when working on spikes or adding new features.
it makes pushing and pulling fast and easy. This reduces the probability of sharing workspaces and allows easy synchronization of new code between developers.
it differentiates between commits (which are local to the current repository) and push/pulls (where code is shared). This encourages developers to commit more frequently, because the fear of "breaking the build" is removed.
it separates the operation of pulling changes from other developers and merging those changes into your own repository. This means that a developer can accept a change to their repository at any time without having to worry about breaking their own build, until such time they are ready to perform the merge.
it enables developers working on a new feature to distribute changes between themselves without affecting the central repository (yes, CRs are allowed in Mercurial, they just don't take as "central" a "role" as with VCS tools). Again, fear of "breaking the build" is completely removed.
it does an outstanding job merging changes, in part because merges occur more frequently than in other systems, and in part because it does have an excellent merge algorithm.

I find it interesting that SCM best practices have been around for many years (the above abstract and its corresponding paper were written over a decade ago), but they are not well understood in the developer community. Developers have been repeatedly told that using some kind of VCS is good, the problem has been simply getting developers on-board with this. SCM suffers because most VCSs available actually discourage their use.

For example, compare Mercurial with Subversion (a popular open-source VCS).

the latter has no cloning operation, to "clone" a repository requires performing a complete checkout of the source tree from the Central Repository [CR]. Checking code out from the CR is a lengthy operation, because full copies of everything has to be transferred (probably across a network) to your development machine.
the Mercurial "clone" operation actually creates a new branch. In Subversion you "copy" an entire directory tree to another location in your repository. The former is local, the latter requires interaction with the CR, which means that a branch in Subversion is forever embedded in the SVN database, even if it was for a spike.
it has no concept of push/pull, you commit code directly to the CR. The only way to get new code to other developers are either through creating and emailing diffs (that may or may not break when applied to their repository, depending on the changes they made) or by committing your changes. The former is painful, the latter raises the specter of breaking the build and is hence relatively distasteful.
it has no concept of a "local" commit, the only mechanism available to the developer to "place a stake in the ground" is to commit code to the CR. Again, this raises the specter of breaking the build.
it requires that changes must be merged prior to the next commit. If you branch then merging isn't required, but branches are more painful to use, and are merged less frequently.

As you can see the central role that the CR takes with Subversion actually hurts. I know from personal experience that I tend to refrain from checking stuff in for long periods of time when working in the Subversion realm. I'm going out on a limb here, but I suspect this is a common problem among developers. We have heard for years that "breaking the build" is bad so the natural tendency is to avoid doing things that might break the build, like committing changes to a CR.

In any case, using Subversion (and similar VCS tools) actually reduces the likely-hood of the developer to use SCM best practices because proper use of the VCS actually encourages you to do things that cause pain. DVCS tools, on the other hand, makes the branching to explore new ideas and add new features a natural, meaningful way of thinking and working with your code. That is the real reason that DVCS tools deserve praise.

Introduction to security via password policies

2010-03-30T19:23:00.007-05:00

Security is an enormously complicated topic and it has a surprisingly large number of subtopics. Security, at the 10,000 meters level, is all about making sure that a person or program (the privileged user) that should have access to some data, information, program, system or physical location (the asset) can obtain such access reasonably quickly and easily, with a common caveat that such access is logged and recorded. Every other individual or program (the attacker) that may deliberately or accidentally attempt to obtain access is "satisfactory" denied, with a similar caveat that as much information as possible about the denied access is also logged and recorded. Here we explore how and why corporations rely on passwords.

Perhaps unsurprisingly this process of allowing one group of individuals access to something, while denying other groups (i.e., everyone else) creates a dichotomy between ease of access and level of protection. The easier you make it for the "good" group to access the protected asset, the less likely it is that you will be able to deny access to every member of the "bad" group (hence the "satisfactory" part in the original definition). If you want to deny access to 100% of everyone in the "bad" group, you are correspondingly going to make it quite difficult for members of the "good" group to gain access. This give and take between the "control" and "access" of controlled access to assets is pretty much true at all levels of security. What this implies is that security is not a destination, it is a multi-layered synthesis of processes and principals all working (hopefully) together for the common goal of protecting assets. For the curious, here is a glossary of security related terms.

With this baseline introduction to security in place, I wish to focus on the security subtopic commonly known as "passwords" (alternative labels include "passphrase," "passcode," "keyphrase", "keys" and several other pseudonyms) In this case the asset protected is typically a digital asset, and the password is the key to the protection mechanism; in such a system passwords are the first (and, unfortunately, often the only) line of defense. A privileged user is authenticated to access the asset (given permission) by virtue of knowing the password. Other users are denied access by virtue of not knowing or not being able to guess the password. Note that access to the protected asset might be obtained through other means, but this would require a detailed discussion of protection mechanisms that is not really suitable here.

Attributes of Effective Passwords

Already we can gain quite a bit of insight into the strengths and weakness of a system that uses passwords to authenticate users.

Passwords are more effective when...

they are more complicated (random) because this makes them harder to guess.
what each one protects is limited in scope because fewer assets protected by the password means less assets are at risk if a password attack is successful.
fewer people know a password because there is less risk of exposure, accidental or deliberate. For critically important passwords this has the disadvantage that an attacker can choose a narrower focus of attack - one reason the U.S. President wanders around with Secret Service bodyguards all the time, a good thing since he holds the primary key to the USA nuclear arsenal.
they are spread across multiple people, because this reduces the risk that one individual can or will abuse their asset privileges if all are required to be present when it is used.
provided to the authentication mechanism in such a fashion as to prevent (or at least make difficult) external observation.
they are not written down, a corollary of the above that helps to make observation of the password difficult.
they are not logged, recorded or stored by the authentication system (not even failed attempts), another corollary to help make observing a password difficult. Passwords are commonly stored using a "one-way" encryption system, this reduces the ability of an attacker to use the encrypted form for purposes of determining a password.
they are changed often, this is because constantly changing passwords prevents an attacker from continuing to use a known password for an unlimited time in the future.

To understand this last point better, consider a credit card. A credit card contains a digital and printed password for accessing your bank account; an individual who can obtain the numbers on both front and back of your card may successfully pass themselves off as you at a wide variety of retailers. They can draw against your account and may continue to do so over and over again until you "change the password" (i.e., call the card issuer and cancel the card). If such a thief is careful in their transactions over a long period of time they can potentially go for months, or even years before the "password is changed." Banks understand this risk, they've seen it before, and their potential liability in such cases is why they periodically "change the password" by reissuing a new card with new numbers front and back on a regular schedule.

Not all of these strengths and weaknesses we just discussed are readily apparent to the normal computer user. It says something about human nature that, on systems that allow users to select their own passwords with no guidance or restrictions on the chosen value, the most common password chosen is "123456" with "password" and "stupid" close runner-ups. This inherent weakness in choosing good passwords is one reason many companies have a "password policy" in place for their computer users.

If you're unfamiliar with the term "password policy" then you should understand that they are a set of guidelines primarily enforced at the computer itself, the use of which is intended to encourage users to create relatively secure passwords. Most modern computer systems contain software that helps IT manage the kinds of passwords that are acceptable and how often the user must change their password. The fact that the computer will do most of the enforcement grunt work makes corporate management of passwords a snap. As an example, here is a password policy that your IT group may enforce:

Password Policy for XYZ Corp:

Must be changed every 90 days.
Must have between 8 and 20 characters.
Must use both lower and UPPER case letters.
Must use at least two digits or symbols.
Cannot be a password you have used in the past.

As you may see, these rules are to address several of the points listed in the "Attributes of Effective Passwords" list above. This policy basically encourages regular password changes and fairly reasonably enforces the creation of complicated passwords. Such a written policy statement is the digital equivalent to having OSHA safety guidelines posted on the company's legal notice board.

If you are a corporation (especially a public corp), the officers of the company actually have a legal obligation to protect the corporate assets, failure to do so (or rather failure to make reasonable attempts at doing so) means that you, the officer, or you, the corporation, can loose all sorts of rights and/or open yourself to all sorts of trouble (often in the form of lawyers serving papers, undesirable stock action or both - multiplexed). A public corporation who fails to reasonably protect its assets is just asking for a shareholder's lawsuit. This protection requirement extends to and includes corporate digital assets (a phrase that really means "bits stored on some hard drive somewhere (and, by the way, the latter had better be owned or controlled by the company, or a serious looking man (woman) in a pinstripe suit (dress) is going to be dispatched somewhere as soon as we know where we're going to send him (her))") and in certain situations may have even more egregious requirements than physical assets. Just examine the actions of the RIAA "on behalf of music artists" for the last decade or two if you don't believe me (what a great business idea, sue your customers).

Strangely, one of the best and easiest ways to show your shareholders (or the judge) that you are taking seriously the protection of your digital assets is to have your IT department put into place a password policy similar to the one above. There is more than this, of course, but a question similar to, "Does your company have a password policy?" will invariably be one of the first questions asked; followed closely by, "What actions does your company take to enforce such a policy?"

Of course, under your newly minted policy the most likely password in the above system may now be "Pa$$w0rd" but at least you tried (besides, the first and last policy guidelines listed above will at least ensure that the obvious alternatives to common passwords will be flushed out of the system fairly quickly).

An IT security professional will need to be careful, however. Aggressive policies can actually work against you. Forcing users to frequently create new passwords increases your chance that they will act against you in other ways (i.e., writing down the password on a sticky note they then tack to the bottom of their screen). The best password systems make as much of this automated as possible.

To reiterate: from the user's perspective, the best system should be an easy to remember password and be trivial to use. From the security perspective: the ideal password is a randomly generated password that may be used exactly once, a different password is required for each successive authentication for an asset. Such a system exists, but the cost is fairly high. Thankfully, competitors are starting to offer lower priced alternatives.

If you are a private citizen you don't have the same legal responsibility to protect personal assets (i.e., someone can steal from you and may be prosecuted even if you didn't lock your front door), and such assets are not normally protected by passwords anyway. This doesn't mean that you should't pay attention to these password issues. You still need to take reasonable action (if only for self interest) in selecting passwords for your bank accounts, utility account, mortgage accounts and any internet retailers you frequent.

An exercise for the reader: are password policies the cause for such idiomatic trash as 1337 $934|< (elite speak)?

Caching ssh private keys using openssh on GNU/Linux

2010-03-29T19:58:00.006-05:00

You probably use ssh on a daily basis, I know I do. I find that many people I talk to don't know that typical ssh installations have the ability to cache their private keys, so they wind up having to type their private key passphrase several times a day. Some people actually get frustrated enough with this process that they remove the passphrase from their private key file entirely. Don't do that! Trust me, there is a safer and better way.

In this article I discuss how to setup GNU/Linux (using openssh) hosts to cache your private keys on startup. I will discuss how to configure Microsoft Windows hosts using Simon Tatham's excellent PuTTY applications in another article.

I set up my more secured environments (from which I ssh to any other machine I require) so that my passphrases are cached in memory using the ssh-agent daemon. Here is what my .bash_profile runs every time I log into my primary GNU/Linux machine.

run_ssh_agent="${HOME}/.ssh/agent-for-${HOST}.pid"
[ -f "$run_ssh_agent" ] && . "$run_ssh_agent" > /dev/null 2>&1
if kill -0 $SSH_AGENT_PID > /dev/null 2>&1
then echo Agent pid $SSH_AGENT_PID
else
    ssh-agent -s > "$run_ssh_agent"
    . "$run_ssh_agent"
    ssh-add
fi
ssh-add -l

This bash script (backwards compatable to sh) starts up and installs your private keys into the ssh-agent daemon. Every time you login to this machine thereafter your shell is configured to use the same agent as before, so you don't need to retype your passphrase until either the daemon is killed or the machine is restarted.

How it works:

Note that the run_ssh_agent shell variable references a host specific file. This file is used to retain shell settings required to contact the ssh-agent key server so that they are accessible across multiple login sessions. We now load these settings and check to see if the ssh-agent key server daemon has already been started using the kill -0 $SSH_AGENT_PID command.

The special environment variables that ssh applications (i.e., ssh, scp, sftp) require from your shell include SSH_AUTH_SOCK and SSH_AGENT_PID. The first references a FIFO located in a secured directory (normally in /tmp) and the second indicates the process identifier of the agent. The ssh applications use the former when use of the private key is required, typically passing the actual authentication work off to the ssh-agent. This script uses the PID variable to determine whether or not the agent is running.

The program ssh-agent is a daemon that stores your private keys on behalf of other ssh applications. The -s option to ssh-agent tells it to dump to STDOUT a script that sets up the above named environment variables for Bourne compatible shells (i.e., bash) and the following line then tells the running shell to evaluates the just-generated script. This loads the SSH_* environment variables into the running shell.

The ssh-add application is then executed. The job of ssh-add is to perform user authentication via the passphrase attached to each private key when it was generated, and then load each corresponding key into the ssh-agent daemon. Finally, after everything has been started or installed the ssh-add -l command is executed to list each identity found in the key server.

After installing the above code in your .profile or .bash_profile you should see something like this the first time you login or run bash -login.

Agent pid 22535
Enter passphrase for /home/kevin/.ssh/id_rsa:
Identity added: /home/kevin/.ssh/id_rsa (/home/kevin/.ssh/id_rsa)
Identity added: /home/kevin/.ssh/id_dsa (/home/kevin/.ssh/id_dsa)
Identity added: /home/kevin/.ssh/identity (kevin@linux)
3072 bb:55:6d:a0:b9:c6:c9:10:03:72:9e:e4:cf:3b:a4:44 kevin@linux (RSA1)
3072 64:42:98:8f:05:8c:a5:df:52:fa:6a:d0:fd:5a:78:bd /home/kevin/.ssh/id_rsa (RSA)
3072 cf:05:ae:d6:91:c0:9b:ce:03:81:88:35:f2:af:c6:49 /home/kevin/.ssh/id_dsa (DSA)

The ssh-add application will prompt for a passphrase for each identity file located in your ~/.ssh directory that has a different passphrase. As you see here, I use the same passphrase on all of my ssh private key files.

Every time you login thereafter you will see something like this:

Agent pid 22535
3072 bb:55:6d:a0:b9:c6:c9:10:03:72:9e:e4:cf:3b:a4:44 kevin@linux (RSA1)
3072 64:42:98:8f:05:8c:a5:df:52:fa:6a:d0:fd:5a:78:bd /home/kevin/.ssh/id_rsa (RSA)
3072 cf:05:ae:d6:91:c0:9b:ce:03:81:88:35:f2:af:c6:49 /home/kevin/.ssh/id_dsa (DSA)

You can now take advantage of these private keys by distributing an associated public key to whom you please. Configure one in your Subversion server so you can use the svn+ssh scheme. Add one to your normal remote machines.

Elegant parallel processes in bash

2010-03-28T23:22:00.009-05:00

Thanks in large part to a desire to facilitate better use of my multi-CPU GNU/Linux system I decided to put together a script that would allow spawning parallel tasks according to a simple template provided on the command line.

The bash shell has been a scripting staple for decades. No other scripting system (no, not even Perl) gives the developer more control over processes, descriptors and pipes as an innate part of the language. The bash shell (its name was originally a pun: the Bourne Again Shell) inherits much of this facility from its predecessor 'sh' (the Bourne Shell). It seemed natural to use the process control facility of bash to build a script that dispatched processes in parallel.

Hunting around I found that several people have done something similar, but looking closely at the scripts on the internet I realized that all were fundamentally flawed in that they all polled the dispatched subprocesses to determine whether they have completed or not. The most egregious of these systems actually used the bash 'wait' command with no arguments, hence requiring all subprocesses to complete before the next batch were dispatched. Unix is a resource sharing system and processes ideally should avoid using any resource unnecessarily. Polling by periodically waking up and seeing if the world has changed is inelegant.

I'm a "make" fan, I wanted something that works just like "make -j 9" but was easier to use such that spawning a multiplicity of commands from a single template should be trivial. Hence I wrote parallel.sh, a short (200 lines, including 50 lines of usage) script that elegantly solves the problem of multiplexing subprocesses. The parallel.sh script blocks (it does NOT poll) waiting until one of its subprocesses completes; at which point it wakes up long enough to harvest the child's result code, read in the arguments for the next pending task, and fork. It does all the right things that a good UNiXy program should do: using only those resources (i.e., CPU, memory, disk) that it must to get the job done and then get out of the way.

What it does:

The parallel.sh script reads one or more lines off STDIN to compose the optional arguments for a command whose template is specified on the parallel.sh command line, and then forks as many subtasks as it can up to a user imposed limit (i.e., -j 4). As each subtask completes it reaps the child and starts a new one until EOF is reached on STDIN, at which point it waits for all child processes to complete and exits.

How to do it wrong:

The easiest (and worst) approach is simply to spawn each child process gunshot style using the '&' background operator:

while read line ; do eval "$line" & ; done

No job control, no resource management, simply shoot the whole wad in one go. What this does is bring your system to its knees if more than 3-5 processes per CPU are spawned. Everything goes slow. The system is constantly context switching and flushing cache lines and if each process is disk intensive you'll quickly bring your entire system to a crawl. The security concerns of exec'ing shell scripts should bother you too (though this article is not about security). Don't do this.

After a child process is successfully started in the background using '&', its identifier is accessible to the parent shell via the '$!' variable. What most people do is spawn the subprocess, store the PID of the spawned process and then periodically wake up and see if the PID is still running. There are several ways of checking that a child process is alive, here are two:

% [[ -d /proc/$pid ]] && echo "child $pid is alive and well"
% kill -0 $pid 2> /dev/null && echo "child $pid is alive and well"

As an example of the prototypical (but inelegant) approach of running parallel processes in a shell script, I give you the naive script that reads commands off STDIN and dispatches up to a "maximum" number of jobs at a time. This is a more practical approach to resource usage than the first example.

maximum=4
declare -a cpids
while read line ; do
    until (( ${#cpid[*]} < maximum )) ; do
        for (( i = 0; i < maximum; ++i )); do
            if [[ ! -d /proc/${cpid[$i]} ]] ; then # or kill
                wait ${cpid[$i]} # harvest child
                unset cpid[$i]
                break 2
            fi
        done
        sleep 1
    done
    eval "$line" &
    cpid=( "${cpid[@]}" $! ) # cpid[${#cpid[*]}]=$! # does not work
done
wait
exit 0

Phew! This probably works, but the logic is fairly complicated. There are several issues that bother me with this code. The 'until' test is redundant after the first iteration. The polling of the subprocesses and sleep is inelegant. This code (as with the first example above) blurs the line between instruction and data. Finally, this is really quite complex code and does not really leverage the strengths of bash.

How to do it right:

The following code is the crux of the parallel.sh script.

# setup a named pipe (FIFO)
myfifo=$( mktemp --dry-run )
mkfifo --mode=0700 $myfifo
exec 3<>$myfifo # hook pipe up to descriptor 3 for read/write
rm -f $myfifo # pipe remains intact until closed
maximum=4 # cpus
running=0
while read line ; do
    while (( running >= maximum )) ; do
        if read -u 3 cpid ; then
            wait $cpid
            (( --running ))
        fi
    done
    ( # child process
        "$@" "$line"
        echo $BASHPID 1>&3
    ) &
    (( ++running ))
done
wait
exit 0

My parallel.sh script actually does a bit more than this, but that is due to some of the other features it supports: template commands (i.e., commands that accept multiple arguments), blocking the output into a log file, option processing (i.e., -j #cpus) and several other items.

So what did I do here? I'm using a named pipe. The pipe is created in your temp directory, and then removed so only this script has access to the fifo. All pipes require a reader and a writer. In this case the reader is the parent process, which allows it to block until a writer sends something through the pipe. The writer is the child process which holds the pipe in escrow until the underlying command in the subprocess completes at which point the PID of the child is written to the fifo and the child exits. Upon EOF the script waits for all children to complete and then exits.

Note also how the command itself is formulated. No longer is the entire command read off of each line from STDIN. Rather the command is entered on the command line itself (under direct control of the developer, rather than trusting a data feed) and each line from STDIN is appended to the end of the command (if you really want the behavior of the first two examples, simply run "process.sh exec").

Cut and paste the above code into parallel.sh, add "#!/bin/bash" to the top, chmod +x process.sh and you now have a basic parallel processing command for your multi-CPU system. You can now run xargs style command sequences in parallel as this version of parallel.sh has similar operating semantics to xargs.

The only additional major feature that I have in my actual parallel.sh script is the ability to templatize specific arguments in the command line, such that each dispatched command may reference multiple lines as individual arguments. For example, I'm able to process images in parallel using ImageMagick and parallel.sh thus:

% /bin/ls my_camera/*.jpg | sed -e 'p;s/camera/website/' |
> parallel.sh -j 8 mogrify -resample 800x600 --write '$2' '$1'

The above command processes all JPEG files in the directory "my_camera" and down-samples them to 800x600, writing the final image into the directory "my_website". A total of 8 processes will be allowed to run simultaneously.

UPDATE: I've uploaded the complete source code of parallel.sh to ActiveState Code.

Welcome to Insights into Software

2010-03-28T19:40:00.001-05:00

Here I will post my observations on software. My primary focus is on GNU/Linux software. This blog is going to be on technical issues of particular interest to software developers.