Rounding function for bc

bc doesn’t include a way to round floating point values to the nearest integer, but you can write one yourself. Just type this in:

define round(n)
{
    oldscale = scale
    if (n > 0)
        value = n + 0.5
    if (n < 0)
        value = n - 0.5
    scale = 0
    rounded = value / 1
    scale = oldscale
    return rounded
}

If you don’t feel like typing this in every time, you can add it to a file that will be loaded when you start bc. Type it into a file, such as $HOME/.bcrc and then add the following to your .bashrc file:

export BC_ENV_ARGS="$HOME/.bcrc"

Advertisements
Posted in Uncategorized | Tagged , | 2 Comments

C++ Assignment Operator or: How I Learned to Stop Worrying and not Check for Self-Assignment

If you’re already here, I’m going to assume you know a lot of the intricacies of writing an assignment operator in C++. Getting all the ins and outs of writing assignment operators is tricky – if you want a good discussion of all the bits and pieces, I’d recommend taking a look at The Anatomy of the Assignment Operator. But that’s not why I’m here, so at the risk of being blasphemous, I’ll just get my main point out of the way.

If you are writing
if (this != &rhs)
in your assignment operator, you are probably doing it wrong, or at the very least, not as right as it should be.

That’s it. Take a deep breath, sit back, relax and just let it settle. I’ve been told to do it this way for years, and you probably have too, so it might be a bit of a shock. But please, please stop telling people to write it this way. It’s important to understand why people do it, but it’s just as important to understand why it’s wrong.

Self-assignment

Let’s look at why people recommend writing this check. Imagine we have the following class:

class Foo
{
public:

    ...

private:
    Bar* myBar;
};

A first attempt at an assignment operator might look like the following:

Foo& operator=(const Foo& rhs)
{
    delete myBar;
    myBar = new Bar(*rhs.myBar);
    return *this;
}

The first thing that we do is delete the old copy of myBar so that no memory is leaked. Then, we make a copy of the right hand side’s myBar. This is where our problems start. What would happen in the above assignment operator if I tried to assign an object to itself? For example, if I wrote the following:

Foo f;
f = f;

In this case, the parameter rhs would be the same as the current object. So when we try to run the line 3 in the assignment operator:

delete myBar;

the rhs’s myBar is also being deleted. So what happens when we try to run the next line?

myBar = new Bar(*rhs.myBar);

We’re trying to access and copy memory that has already been deleted. At this point, any number of things could happen. Some of the time, that memory will still belong to our process and will be unchanged, and our program will happily continue. But once in a while, the program will mysteriously crash. Trying to debug this issue when it works 99 out of 100 times is difficult and irritating.

So what can we do instead? The commonly suggested solution is to check for self-assignment and skip the allocation and deletion in that case. This does solve the problem, but let’s take a step back and look at our code again. The problem with self-assignment in the above constructor is that by the time we are ready to copy the Bar object, we’ve already deleted it. But what if we did the copy first, swapped that copy with our member variable, and then deleted what used to be our member variable?

Here’s a new code snippet that does that instead:

Foo& operator=(const Foo& rhs)
{
    Bar* temp = new Bar(*rhs.myBar);
    swap(temp, myBar);
    delete myBar;
    return *this;
}

What happens now if we accidentally do self-assignment? Well, line 3 makes a copy of the member variable. Line 4 swaps the copy with our member variable. Finally, line 5 deletes what used to be our member copy. No memory is leaked, no deleted memory is accessed, and at worst, some cycles are wasted making a copy of some memory and deleting it. We fixed the problem without ever needing a check for self-assignment!

But just avoiding a special case doesn’t necessarily make this version better, does it? Well…

Exception guarantees

In C++, there are several guidelines you should try to follow whenever you’re writing a function. These are known as exception guarantees. In some cases, it is impossible to implement the stronger ones, but you should try to implement them if you can.

The first guarantee is the basic guarantee which states that your code should not leak memory if any exceptions are thrown. In both our copy constructors, the only line that could throw an exception is the memory allocation. If it does, then there is no memory cleanup required because we’re only trying to allocate a single object. If our class did have more objects, we would need to allocate them sequentially, catch any exceptions that might be thrown while making copies of them and delete the copies that we had made so far before rethrowing the exception.

The second guarantee is the strong guarantee which states that your code should leave the object in a consistent state if any exceptions are thrown. Let’s imagine that I was using the Foo class in the following context:

do
{
    try
    {
        Foo f1, f2;

        ...

        f1 = f2;

        ...

    }
    catch (bad_alloc& e)
    {
        // Clean up some memory and keep running
    }
} while (!done);

Here, we have a long running process and that may run out of memory at some point, but we have a way of cleaning up some memory if an error ever does occur, so we’d like to continue running the process until it successfully completes.

Now imagine what happens with our first assignment operator. We first delete the member variable myBar, then try to make a copy of the right hand side’s myBar. If this throws an exception, then our Foo will be left with myBar pointing at some invalid memory. When our program tries to pick up where it left off, it will try to access that memory and will probably crash.

What about with our second assignment operator? We first try making a copy of the right hand side’s myBar. If it throws an exception, our Foo is left unchanged. The program can run the loop again and nothing crashes.

By doing any allocations before deleting objects, we’ve managed to avoid the problems of self-assignment without writing if (this != &rhs) . In addition, this code implements the strong guarantee and is therefore safer. If your code relies on a check for self-assignment for correctness, then it probably doesn’t implement the strong guarantee and is less safe than it should be.

But what about speed?

One question I’ve received when explaining this concept is that the second version is much slower when doing self-assignment than the original version. That is true – comparing two memory addresses is much less costly than allocating and deleting memory. However, in practice, self-assignment is generally rare. Optimizing one specific rare case at the expense of the much more common general cases will likely not gain you much. Putting in a special case to guarantee that your program does not crash 1 out of 1000 times is important; putting in a special case to optimize 1 out of 1000 cases is not. If you are concerned about speed, profile your code first and determine how often self-assignment really occurs.

Alternatives

It turns out that there is an even easier way to write an assignment operator as long as certain conditions are met. The strongest exception guarantee is the no-throw guarantee which states that no exceptions will be thrown. As long as we’re not allocating any memory or other objects, this should be possible. In Foo, the only member variable we have is a pointer. Because moving pointers will not throw an exception, we can write a member swap() method as part of the Foo class that swaps the contents of two Foo objects that has the no-throw guarantee. Then, we can write the whole copy constructor as follows:

Foo& operator=(Foo rhs)
{
    swap(rhs); // Calls Foo::swap
    return *this;
}

Rather than sending the right hand side object by reference, we send it by value; this causes the compiler to make a temporary copy of the the right hand side object using Foo’s copy constructor. This temporary object will be sent to the method, and the copy will be swapped with the local object. Then, upon exiting the method, the temporary object will go out of scope and be automatically destroyed. And so, without doing any extra work, we automatically get the basic and strong guarantees.

Posted in Uncategorized | Tagged , | 5 Comments

AutoSSH Module for Prey

Prey

Prey is software that allows you to track computers and other devices in case they are stolen. After it’s installed on a machine, it periodically checks to see if you have reported it as stolen, and if you have, it will contact you with details about the machine’s current status. This information includes its IP address, GPS position, a screenshot of the current desktop and a picture (or video) of the perpetrator using the webcam.


This makes it much easier to recover your property. However, I also wanted to be able to have full control of the machine in order to access my data and to be able to directly monitor the thief. The easiest option is to ssh directly into the machine; however, this is only possible if the router they are connected to doesn’t block outside connections. One solution is to set up Prey to open a remote port on another machine that forwards back to itself; this way, your laptop initiates an outbound connection and evades the block.

Prerequisites

To accomplish this, you will need root access on a server that’s running OpenSSH so that you can add a user that’s only used for Prey. You could conceivably use your own account instead of creating a new one, but if your laptop is stolen, the thief would be given full access to your account. Your laptop also needs to be running Linux (the same procedures should work for other *nix systems, but modifications will have to be made to the directory structure of the download).

Account preparation

To allow Prey to access your server, we will be setting up SSH keys that allow automatic login onto a server. Because of this, it is very important that you create a new user on the server and disable their shell, so that if your laptop is stolen, the thief won’t be given access to an account.

On the server, run the following as root to add a new user:
root@server:~# adduser preyuser
Set a password and whatever other options it asks for.

On your laptop, run all of the following commands as root:
root@laptop:~# ssh-keygen -t rsa
Do not enter a passphrase.
Now use ssh to create a ~/.ssh directory by running:
root@laptop:~# ssh preyuser@server mkdir -p .ssh
Enter the password for the user you just created.
Now append the laptop’s public key to the authorized keys on the server:
root@laptop:~# cat ~/.ssh/id_rsa.pub | ssh preyuser@server 'cat >> .ssh/authorized_keys'
You should now be able to log into the server as preyuser without entering a password.

Finally, back on the server, disable preyuser‘s ability to login by disabling their login shell:
root@server:~# which nologin
/usr/sbin/nologin
root@server:~# chsh -s /usr/sbin/nologin preyuser

Trying to log into the server should now give give you the message that the account is currently not available.

Configuring your laptop

The only thing to do now is to configure Prey. Download the AutoSSH module onto your laptop and decompress it:
root@laptop:~# wget http://www.skari.org/blog/prey-autossh.tgz
root@laptop:~# tar -xzvf prey-autossh.tgz
Edit the autossh/config file and fill in your server, username, and remote port. When you’re done, move the folder into the Prey modules directory:
root@laptop:~# mv autossh /usr/share/prey/modules/
That’s it!

Prey should now open a forwarded tunnel from your server to your laptop when activated. However, if the connection is interrupted, the tunnel will die. You may want to consider installing autossh which will start and actively monitor an SSH connection and restart it as necessary. This module will use autossh if it is available and fall back to plain ssh otherwise.

Logging into your stolen laptop

Now, if your laptop is stolen, Prey should activate and send you a report. To access your laptop, login to your server and run:
user@server:~$ ssh user@localhost -p port

Enter the laptop’s user‘s password,and you should be in. Now go catch the bastard!

Posted in Uncategorized | Tagged | 2 Comments

No sound for Flash in OpenSuse 11.2

I installed OpenSuse 11.2 on my laptop and everything was working fine. except I wasn’t getting any sound out of Flash (e.g. Youtube). Sound was working fine in other programs, so I knew my sound card was working. The problem was, alsamixer had my Pulse Code Modulation muted. To fix it, just run this in a terminal:
alsamixer
and move over to PCM with the arrows and hold the up arrow until it’s maxed out. Hopefully that will fix your problem!

Posted in Uncategorized | Tagged | Leave a comment

A Subversion Pre-Commit Hook

Subversion allows you to run commands, called hook scripts, whenever actions take place in your repository. The most useful of these that I’ve found is the pre-commit hook, which allows you check a transaction for problems before it is committed.

Word Aligned has an excellent introduction on setting up pre-commit hooks and includes a small example. I use a more complex script on my own server, and thought it might be of use to somebody else. It verifies the following:

  • The commit message is at least 10 characters long
  • The commit message is different from the previous message (handy when hit the up arrow and accidentally try to commit again)
  • Tabs are used for indentation instead of spaces (sorry, I’m a tabs guy – you can change it if you need to)
  • PHP files don’t have syntax errors
  • C and C++ files don’t have any digraphs or trigraphs

#!/usr/bin/python
import sys

# These should point to the respective commands
SVNLOOK = '/usr/bin/svnlook'
PHP = '/usr/bin/php'
MIN_MESSAGE_LENGTH = 10

# Gets a command's output
def commandOutput(command):
	import subprocess
	process = subprocess.Popen(command.split(), stdout = subprocess.PIPE)
	return process.communicate()[0] # 0 is stdout


# Returns an array of the changed files' names
def getChangedFiles(svnPath, transaction):
	# Run svnlook to find the files that were changed
	output = commandOutput('%s changed %s --transaction %s' % (SVNLOOK, svnPath, transaction))

	# The output from svnlook looks like the following:
	# U   folder/file1.cpp
	# A   folder/file2.cpp
	# where U means updated and A means added
	def changed(fileName):
		return len(line) &gt; 0 and line[0] in ('A', 'U')
	changedFiles = [line[4:] for line in output.split('\n') if changed(line)]

	# svnlook inserts an empty line, so output.split() will have an extra
	# line with nothing in it - ignore the last lines if they're empty
	while 0 == len(changedFiles[-1]):
		changedFiles = changedFiles[:-1]

	return changedFiles


# Checks that the message is a minimum length
def checkMessageLen(svnPath, transaction, minLength):
	# Run svnlook to get the message log
	output = commandOutput('%s log %s --transaction %s' % (SVNLOOK, svnPath, transaction))

	if len(output) &lt; minLength:
		sys.stderr.write('Message must be at least %d characters\n' % minLength)
		return 1
	else:
		return 0


# Checks that the message is different from the last message
def checkRepeatMessage(svnPath, transaction):
	# Run svnlook to get the message log
	output = commandOutput('%s log %s --transaction %s' % (SVNLOOK, svnPath, transaction))

	currentMessage = output

	lastRevision = int(transaction.split('-')[0]) - 1

	# Empty repositories have no messages
	if lastRevision  0:
			sys.stderr.write('Regex \'%s\' matched \'%s\' on line(s): %s\n' % (regex, fileName, badLines))

	return matches


# Checks a PHP file for syntax errors
def checkPHPSyntax(svnPath, transaction, fileName):
	# Run svnlook to get the file contents
	output = commandOutput('%s cat %s %s --transaction %s' % (SVNLOOK, svnPath, fileName, transaction))

	# Run PHP syntax checking on the file contents
	command = (PHP, '-l')
	process = subprocess.Popen(command, stdin = subprocess.PIPE, stdout = subprocess.PIPE, stderr = subprocess.PIPE)
	output = process.communicate(fileContents)[0]
	process.wait()

	if 0 != process.returncode:
		sys.stderr.write('Found syntax errors in \'%s\':' % fileName)
		# Print the offending lines that were returned from php -l
		for line in output:
			sys.stderr.write(line)
		return 1 # Error found

	return 0 # No errors


svnPath = sys.argv[1]
transaction = sys.argv[2]
files = getChangedFiles(svnPath, transaction)

errorCount = checkMessageLen(svnPath, transaction, MIN_MESSAGE_LENGTH)
errorCount += checkRepeatMessage(svnPath, transaction)

for file in files:
	# Prefer tabs for indentation
	# Skip .txt files
	if not file.endswith(".txt") and not file.endswith(".sql"):
		errorCount = errorCount + stringsInFile(svnPath, transaction, [' {4}'], file)

	# Check PHP syntax
	if file.endswith('.php'):
		errorCount += checkPHPSyntax(svnPath, transaction, file)

	# C and C++ files should not use digraphs or trigraphs
	digraph = '%s|%s|%s|%s|%s' % ('&lt;:', '', ':&gt;', '%:')
	trigraph = '\?\?[=/\'()!-]'
	if file.endswith(('.c', '.cpp', '.cxx', '.cc', '.C', '.h', '.hpp')):
		errorCount += stringsInFile(svnPath, transaction, [digraph, trigraph], file)

sys.exit(errorCount)
Posted in Uncategorized | Tagged | 2 Comments

Compression before encryption

If you’re going to be compressing and encrypting some data, you should do the compression first. Why? There are several reasons:

  • Compressing it last won’t reduce the file size much. Good encryption should make any input data (especially redundant data) appear random. But compression works by removing redundancy, and doesn’t work well on random data. You can see a good example of this here, where encrypting a file and then compressing it actually made it larger than the original!
  • Compressing it should decrease the effectiveness of some attacks. Compression works by reducing the redundancy in the data. A common cryptanalysis method is frequency analysis, which relies on finding repeated data. Compressing it should reduce its effectiveness!
  • Brute force attacks will take longer. Brute force attacks work by trying various keys and decrypting the data and checking if the output data makes any sense. By compressing it first, an attacker must decrypt the data and then decompress it before seeing if the output data makes any sense. This takes much longer, and if an attacker doesn’t know you’re compressing the data at all, they might never break the encryption.

I wanted to see how effective the third point was, so I wrote a Python script that encrypted a short message and used a brute force attack to break it. Then I repeated the experiment, but compressed it using gzip before encrypting it. Here’s how long it took on average, in seconds, to guess a single password:

Password length: Zipped: Not zipped:
2 letters 0.021 0.002
3 letters 0.546 0.061
4 letters 13.612 1.551

As you can see, compressing it before encrypting it took about 9 times as long to break.

Details: A short message was chosen, specifically, “a message“, to encrypt. Because gzip is a block compression algorithm, an attacker only needs to decompress the first bytes rather than the whole file, so I wanted to keep the message short to simulate this. I used 128-bit AES, using a password with only lower case letters. In each iteration, a random password was chosen and both the zipped and unzipped versions were tested. The test was run 1000 times for each password length.

Posted in Uncategorized | 2 Comments

Test MySQL password strength

Newer versions of MySQL stores passwords using a double SHA-1 hash. Because of this, administrators can’t tell what someone’s password is. What if you want to make sure no users are using weak passwords?

This is a simple Python script that will connect to your local MySQL database, pull out the password hashes for all users, and either run a dictionary search or a brute force search on it. Either give it an argument for the dictionary file, or give it a number for the length of passwords you want to test. If you want to use a different character set (e.g. include special characters), change the characterSet variable near the top of the script.

On my system, I was able to test around 50,000 words per second. Note that this cannot be used to recover the root MySQL password, as it requires the root password to connect to the database in the first place.

#!/usr/bin/python
 
import MySQLdb
import sha
import sys
import os
import getpass
 
alpha = "abcdefghijklmnopqrstuvwxyz"
numbers = "0123456789"
# Set this to a string with the character set you want to check
# Examples:
characterSet = alpha
#characterSet = alpha + alpha.upper()
#characterSet = numbers
#characterSet = alpha + alpha.upper() + numbers
 
def recurse(width, logins):
  for i in range(0, width + 1):
    print "Checking width %d" % i
    recurse2(i, logins, 0, "")
    print ""
 
def recurse2(width, logins, position, string):
  for char in characterSet:
    # Show progress
    if position == 0:
      print char,
      sys.stdout.flush()
 
    if (position < width - 1):
      recurse2(width, logins, position + 1, string + char)
    else:
      hash = sha.new(sha.new(string + char).digest())\
          .hexdigest()
      for login in logins:
        if hash == login[2]:
          print "\n'%s'@'%s': '%s'\n" %\
              (login[0], login[1], string + char)
          logins.remove(login)
 
if len(sys.argv) > 1:
  password = getpass.getpass('Enter the root password: ')
  conn = MySQLdb.connect(host = "localhost",
    user = "root",
    passwd = password,
    db = "mysql")
  cursor = conn.cursor()
  cursor.execute("SELECT User, Host, Password from user;")
  logins = cursor.fetchall()
  cursor.close()
  conn.close()
 
  # Preprocess the logins
  processed = []
  for login in logins:
    ignore = False
    # Ignore empty passwords
    if 0 == len(login[2]):
      print "'%s'@'%s' has empty password, ignoring" %\
          (login[0], login[1])
      ignore = True
    # Ignore duplicates
    for p in processed:
      if p[2] == login[2][1:].lower():
        print "'%s'@'%s' has same password as '%s'@'%s', ignoring" %\
            (login[0], login[1], p[0], p[1])
        ignore = True
    if not ignore:
      processed.append((login[0], login[1], login[2][1:].lower()))
 
  if os.path.isfile(sys.argv[1]):
    f = open(sys.argv[1])
    lines = f.readlines()
    f.close()
 
    for line in lines:
      hash = sha.new(sha.new(line[:-1]).digest()).hexdigest()
      for login in processed:
        if hash == login[2]:
          print "'%s'@'%s': '%s'" % (login[0], login[1], line[:-1])
          break
  else:
    try:
      depth = int(sys.argv[1])
    except:
      print "Usage: %s [dictionary file | brute force depth]" % sys.argv[0]
    recurse(depth, processed)
else:
  print "Usage: %s [dictionary file | brute force depth]" % sys.argv[0]
Posted in Uncategorized | Tagged | Leave a comment