As it turns out random geometric graphs (RGG) are extremely good at modeling wireless sensor networks. This is because an RGG's edges are determined by a vertex's proximity to another vertex. These two vertices have an edge between them if they are less than some distance r from each other. In this case r is an analog to the broadcast radius of a wireless sensor. In a real world wireless sensor network, sensors may be dropped from a plane or scattered on the ground in some unpredictable fashion. It is useful to be able to create a communication backbone between these sensors so that you can extract data from all the sensors from only one (or very few) egress sensors. Imagine that it would be much nicer to walk to and download information from one sensor than to gather information individually from all sensors that are scattered throughout some arbitrarily large geographic area. Using "smallest last ordering" and graph coloring algorithms were able to reliably choose pretty good backbones, using a program and any random geometric graph as input. This project was extremely in depth so I recommend that you click here to explore the project further and read the whole project description as well as check out the cool visualizations I made to display the work that has been done.

This project has to be one of the coolest that I worked on at University. The task was centered around reliably finding high quality communication backbones in a wireless sensor network. This is becoming increasingly relevant as IoT devices are becoming cheaper and more ubiquitous by the day. Consider an example where thousands of wireless sensors are thrown out at random across a planet's surface. It would be very costly and time consuming to travel to each individual sensor and extract its stored information. Instead it would be vastly superior if it were possible to extract information from the entire network from only one single egress point. To do this we need to establish communication backbones that will identify routes for this information to flow out of the network.

To simulate the behavior of such a network, we used random geometric graphs (RGGs). RGGs have the property that a vertex is connected to another vertex if it is within some distance R of each other, where R is a configurable distance and is a very apt analog to broadcast range on a wireless sensor. Then using a pretty massive series of graph algorithms to color, order and select nodes, we generate some viable backbones. To give you an idea of how this works, we first perform a "Smallest Last Ordering" of the nodes in the graph and then color them based on this ordering. This ordering and then subsequent coloring allows us to identify maximum independent sets of nodes with a bias towards high degree nodes. This means that colors generated early (color 0 in terms of the Grundy coloring algorithm) will generally have many many nodes in it with extremely high set coverage. We can then combine any two of these independent sets and pick the ones with the highest overall set coverage (and potentially fewest number of vertices). This is best demonstrated by example. Please watch the following video visualizing the results on a unit sphere.

sphereVisualizationDemo from Tyler Springer on Vimeo.

This project has two major components:

• The Visualization Component
• The Computation Component

Visualization was done entirely using the Processing language by reading in data that was pre-generated by the Computation Component. The visualization component is demoed above, but only results for the sphere is shown. In addition to a sphere, I also tested graphs with points thrown onto a unit square and also a unit disk. Here are some sample images of those in action:

And here is a communication backbone generated for this graph (it has 99.95% set coverage).

And here's a graph on a unit square just because it looks pretty:

The computation component is responsible for actually creating all this data. Is is a python/C program (using Cython to expedite the process of writing a C extension) that creates a number of CSV files that are then visualized by the Processing sketches shown above. This program is a command line utility that I created to nicely and quickly generate all the required data for a simulation. Input parameters include the number of nodes, the type of projection (square, disk, sphere), the evaluation method, the average degree of nodes within the graph and the location where you'd like the files written to.

One other interesting feature of this program is that there are a number of optimizations to help reduce computational complexity (this really helps when graphs become large). For example, when generating graphs we must compare the distance of each node to every other node in order to determine whether or not they are less than or equal to a distance R from each other and thereby have a connecting edge which given n nodes will take n^2 comparisons to evaluate, or O(n^2). That's not a great running class to be in, so instead it make a lot more sense to optimize this process. Given the observation that nodes that are greater than a distance R from each other cannot be connected, it doesn't make a lot of sense for nodes on opposite sides of the graph to be compared as its physically impossible that they are connected. So instead it is much better if we divide the graph up into a grid where each cell is RxR in size. We then compare the nodes only within that cell to each other eliminating silly comparisons that will objectively never result in an edge between vertices. This process runs in O(n^2 r^2) where R is less than 1. This is only one example of optimizations that makes this a tractable problem and one that can actually be implemented in the real world.

The post below is the actual document I submitted for my project and is chock full of more details about this whole process. Please take a moment to read through it as you might learn something interesting!

This project was a joint effort between my Dad and myself (and a few errant friends toward the end) as there was a lot that had to be done. The wood is actually from an old bookshelf that my Mom and Dad bought for my apartment during school. It was $10 and made from solid oak, so the lumber alone made that shelf a good investment. The shelf was stained and had to be completely resurfaced before we could cut it down, and stick it all back together as a coffee table. Everything uses pocket screw so that there are no exposed screw heads and the table has 6 layer of polyurethane coating the surface (4 regular fast dry poly and 2 spar to protect the wood from UV and moisture).

The LEDs are APA102 based and were purchased from Pololu electronics. These particular LEDs are the highest-density APA102s that I am aware of on the market at 144 LEDs per meter. However they are only sold in half-meter strips due to voltage drop across the strip (yes, they are super super bright), which means you have to put a bunch of strips together and then power each one individually to prevent the color from becoming increasingly red. At the moment, the LEDs are driven by an Arduino UNO via standard SPI, though I plan to swap that out for a Raspberry Pi any day now. The Pi will let me do really cool things like slice up images and use them as a bit stream of colors to the LEDs (if that makes no sense watch this video to get an idea of what I mean).

Here is quick view of the finished product:

Here are some videos of the table in action:

Infinity Table Running In the Living Room from Tyler Springer on Vimeo.

Infinity Table Running Before Urethane from Tyler Springer on Vimeo.

First look at the LEDs and Mirror from Tyler Springer on Vimeo.

Quick test fit of the LEDs and the mirrors from Tyler Springer on Vimeo.

Playing with the spacing on the LEDs from Tyler Springer on Vimeo.

Annnnnd here is the table being built over the course of probably about 6 months, as we had time:

AWS is a tremendous resource that makes standing up and shutting down complex infrastructure easy. At work and at home I use AWS on an almost daily basis. I like that I can provision and terminate resources without giving a second thought to the location or content of the physical machines, and that I can do so inside of 60 seconds for just about any action.

In the past I've never had to consider what happens to something like an EBS volume when its returned to the Amazon resource pool, because frankly who cares? It doesn't bother me that someone at Amazon might be able to see the content of my volume because at the end of the day all they are going to find is some code. But what happens if our volumes do in fact contain confidential information or even worse, confidential information that is worth something to someone like a hacker?

In those instances it is reasonable to protect the content of the volumes by encrypting them (a feature that Amazon offers free of charge). In which case you can simply destroy the keys encrypting the drive and rest easy that no one, at Amazon, or anywhere else is going to be able to snoop on the contents of the volume once its returned to the resource pool.

However, in the real world, things have a tendency to be a little more screwy. Consider that someone other than yourself could have spun up an environment at your company that was never intended to contain any kind of sensitive/confidential information. In this case it is completely reasonable to have setup unencrypted volumes, if for no reason other than to have one less key to manage. Now let's say that at some point, someone places customer data on those volumes for demo purposes. This shouldn't have happened, but let's say it did anyway. Some questions you might then ask are:

• What happens to the data when it is released to Amazon?
• Is your data secure?
• Do you have to worry that your data might be persisted and another customer down the line might have access to it?

As it turns out the answers to these questions can be a little tough to come by. After quite a bit of searching, I found this AWS developer forum thread detailing different compliance ratings that Amazon holds and how it deals with your data during its tenancy in AWS. Most of the information in this thread seems to indicate that data is wiped according to DoD standards and that you have absolutely nothing to worry about when releasing volumes containing sensitive information. However, this is misleading and is not necessarily the case. If you read the very final post in the thread you will see that page 21 of the AWS security whitepaper reads:

"Amazon EBS volumes are presented to you as raw unformatted block devices that have been wiped prior to being made available for use. Wiping occurs immediately before reuse so that you can be assured that the wipe process completed. If you have procedures requiring that all data be wiped via a specific method, such as those detailed in DoD 5220.22-M ("National Industrial Security Program Operating Manual") or NIST 800-88 ("Guidelines for Media Sanitization"), you have the ability to do so on Amazon EBS. You should conduct a specialized wipe procedure prior to deleting the volume for compliance with your established requirements."

This indicates that the responsibility of deleting data on EBS volumes to DoD or NIST standards is in fact the customer's responsibility and is not inherently performed by AWS. This statement is also mirrored in AWS' shared responsibility model documentation which indicates that customers are responsible for security in the cloud and AWS is responsible for security of the cloud. So, if you don't ensure drives are properly wiped before releasing them back into the AWS resource pool the data is still hanging around within the cloud and is not deleted until the space is needed for another customer. This makes your sensitive data susceptible to exfiltration by Amazon contractors or employees (and although I'm sure they're all honest, you never can be too sure).

So in conclusion, we must securely wipe all data from EBS volumes before releasing them back to Amazon if we want to ensure that our potentially sensitive data doesn't fall into the wrong hands.

Introducing The GNU Shred Utility

The GNU shred utility makes it possible to permanently erase all data on a persistent memory device like a hard drive or solid state drive. This is achieved by overwriting the contents of the volume with random data in several passes and then finally zeroing out everything in a final pass to produce a raw, unformatted, volume free of any sensitive/confidential information. shred is part of coreutils so finding quality documentation should be as easy a man shred. However, there are a number of good blog posts about how to use shred and how it works under the hood if you are inclined to find more information. Let's see how we can use shred to wipe an EBS volume so that we can safely release it back to the AWS resource pool.

Enter python + boto

In order to use shred we have to take care of a few things first. First and foremost it is not possible to reliably destroy an EBS volume that is currently attached to an EC2 instance. Instead when we stop/terminate the EC2 instance we must ensure that the EBS volume attached to it is not destroyed by default (otherwise the EBS volume is released to AWS before it has been shredded). Once the EC2 instance is stopped/terminated the EBS volume can/will be unattached and is ready to be shredded.

Because we can not shred a drive that we are booting from we will need another auxiliary EC2 instance to actually perform the shred. It is also mandatory that the new EC2 instance is setup within the same availability zone as the EBS volume to be shredded (this way Amazon avoids shipping data around and using up its internal bandwidth).

Once we have configured and launched a new EC2 instance we are ready to start shredding some drives. To establish some basic understanding of the process lets look at how we can perform this task manually, then we will automate the process using python and boto which is much more convenient for shredding multiple EBS volumes. To get started shredding we will need to:

• Attach the EBS volume we want to erase to the new EC2 instance we have setup for shredding
• Locate that attached volume in /dev/, but do not mount it
• Run shred on the attached EBS volume
• Detach the drive from EC2 instance
• Release the EBS volume back to Amazon's resource pool

So, let's go ahead and attach the EBS volume we want to shred to the new EC2 instance we've setup. First, go to the AWS management console and copy down the "instance id" field (it should have the form "i-abcd1234"). Next select "volumes" from the "Elastic Block Store" section of the navigation menu on the left side of the window and locate the volume you intend to shred. Right click the volume and select "Attach volume." A dialog box will appear, prompting you to enter the instance id of the machine you want to attach the drive to - enter the instance id that you copied down earlier. This prompt will also ask you for "device." This field is the name you want the drive to have when it appears in /dev/. You can use whatever you want, but I normally use /dev/sdx. This particular device name will be converted to /dev/xvdx on the actual EC2 instance (I couldn't tell you why). So now that the drive is attached, ssh into the newly created EC2 instance and run ls -l /dev/ and confirm that xvdx or whatever you named your device is present in the list. To make your life a bit easier you can run ls -l /dev/ | grep xvdx which will search specifically for xvdx instead of having to manually look through the list.

Once you have confirmed that the device is attached, we can go ahead and start shredding. You do not need to mount the drive to shred it. To shred the drive to DoD standards simply run the command:

sudo shred /dev/xvdx -f -v -z

This will shred the device /dev/xvdx with three passes (default) of random data plus one final pass of zeros to finish it out. 3 is the standard number of iterations that shred will perform, but you can specify any number you want using the -n flag. So sudo shred /dev/xvdx -n 7 would write 7 passes of random data to the drive.