VirtuaBoard – CS 152B Final Project

Posted on June 13, 2012 by Sam

CS 152B is the second Digital Design Laboratory offered by the Computer Science Department at UCLA. As it is a capstone course for CS and CSE majors, it involves a long, challenging project. In the video below, you can see a demonstration of our project.

IMGP2457 small VirtuaBoard CS 152B Final Project

VirtuaBoard is a system for developing grid-based games controlled by position-detection. The system consists of a basic camera, a screen, and a Xilinx Virtex II Pro with a Digilent video capture module. The Xilinx Virtex II Pro is a board containing an FPGA and a PowerPC processor. The FPGA does basic image-processing on the image received from the camera and forwards coordinates of the detected object to the PowerPC processor through a GPIO. The processor executes software implementing the game logic and display.

As a proof-of-concept for the system (calibration, position detection, and software library), we implemented two games: Connect 4! and Tic-Tac-Toe. The software library allows for input calibrated to a grid with a specifiable number of rows and columns, a required hover time, and display of the currently-detected calibrated position (the little red “X” that shows up). For our implementation, we used grids of three different sizes: 2×1 (game selection menu), 3×3 (Tic-Tac-Toe), and 7×6 (Connect 4!). We also required a hover time of 1 second (verified every tenth of a second) to make a selection. This allowed for good responsiveness while reducing the number of false selections.

Experiments in Parallelism – Corner Detection with the Moravec algorithm

Posted on June 7, 2012 by Sam

After an incredibly long hiatus, I’ve decided to write a little about my final project for CS 133 – Parallel and Distributed Computing with Adam Kaplan.

In this course, the final project was to implement a number of different image processing algorithms sequentially and to parallelize these algorithms. For my part in the group, I chose to implement corner detection.

CS 133 focuses on a number of different parallel programming frameworks as well as different methods for breaking tasks up among multiple processes. For this final project, I decided that OpenMP was the best solution, as it is well suited to data decomposition and provides a relatively simple way to specify parallel behavior.

In researching existing algorithms which perform corner detection, I came across the Moravec corner detection algorithm. This is one of the older corner detection algorithms, but it seemed to me that it was relatively easy to parallelize, as it makes decisions on a pixel-by-pixel basis. A good explanation of the algorithm is located here.

After parallelizing the algorithm, there was noticeable improvement:

graph 300x175 Experiments in Parallelism Corner Detection with the Moravec algorithm

Speedup vs. Threads for execution of the Moravec algorithm on a 16-core machine

This graph documents the speedup vs. number of threads for execution of this parallel Moravec algorithm on a machine with 16-cores.

Protecting passwords from statistical-guessing attacks

Posted on July 20, 2010 by Sam

A new paper by Stuart Schechter from Microsoft Research, Cormac Herley from Microsoft Research, and Michael Mitzenmacher from Harvard University titled “Popularity is everything” discusses a new method for protecting passwords from statistical-guessing attacks.

The main concept behind the paper is that the most common type of attack against a password-protected system is a brute-force attack which relies on a popularity-sorted dictionary. The proposed protection is to prevent any password from becoming popular enough that a statistical attack is likely to succeed.

There are a number of problems with this idea, however. First, a goal would likely be to prevent any password similar to a popular password from being used. However, if passwords are stored as hash-values (or salted hash-values) there would be no way to compare and find similarity. Storing the passwords as plain-text would solve this problem but introduce a vulnerability if the attacker obtained the password-database. Second, if the popularity is stored as a numeric value an attacker who obtains the database can determine that N users have the same password and use that information to pick a likely passwords. Similarly, an attacker can attempt to create a new password and determine if that password is popular by consulting the database, which would allow the attacker to concentrate on only the most popular passwords.

Herley, et al address these issues by proposing that popularity be stored as a count-min sketch and ensuring false-positives in the data. The count-min sketch is a data structure which relies on the results of multiple hash functions. An array is kept for each hash function recording the number of times that particular hash-value is used. When checking if a password is popular, the lowest number of times reported for the hash-value determines the number of times the password has been used. Collisions in the hash functions allow protection against similar passwords (see Figure 2). This number can be compared against a threshold to determine if it is too popular. False positives in the data help insure that an attacker who gains access to the sketch will not be too greatly aided (section 3.3). False positives are contributed by the collision in hash functions as well as restricting the counters in the sketch to have a maximum increment. Passwords which use these counters will all appear equally popular, forcing an attacker to waste time trying all of them.

A problem with this approach is that the number of organizations which can create an effective popularity count-min sketch is limited to organizations with a large number of users. A possible solution would be to have a shared count-min sketch among organizations, but that would make it easier for an attacker to obtain.

A proof-of-concept implementation of a count-min sketch will follow soon.

Adventures With VPython – Pong

Posted on March 8, 2010 by Eric

So, it’s been a crazy quarter here at UCLA – general education really is a giant time sink. Thankfully, that’ll be done after this quarter and I’ll hopefully have more time to do inane side projects like the one I’m going to talk about today.

Everyone knows about Pong – the little game that you all played on your TI-83 in high school when you were supposed to be paying attention in math class. Along with all the other games you played on your calculator – I’m hoping to play with those later. Anyway. I’ve always had an interest in 3D graphics and how they relate to games. I did some dabbling in OpenGL last summer and it was painful to say the least. I’ve also been dabbling with Python lately, so the next obvious step was to figure out how to do graphics in Python. There a lot of libraries to do this (pygame comes to mind), but I decided to use VPython. It provides all sorts of nice little things – namely the code to construct a shape.

from visual import *
square = box( pos = (0, 0, 0), size = (3, 3, 3), color = color.green)

Nice. You can give the box a velocity by doing something like:

box.velocity = vector( 5, 0, 0 )

Then you can update the position of the box accordingly using your basic physical relationships. You know, Vf = Vi + at, and all the other stuff you learned in physics. Unless you took Physics 1A with Professor Corbin at UCLA, in which case you learned all sorts of other cool stuff and aren’t sure how you passed the class. But I digress.

I started this project just trying to learn how VPython works, and I ended up implementing a version of Pong that is playable, but slightly boring. There is no score display, end-of-game info is displayed in the console, and there is no vector math implemented. Therefore, the ball always bounces at a 45 degree angle from the wall or the paddle. This is both unrealistic and boring. I’m no mathematician, and I don’t currently have the time to implement the vector math. I’ll leave that as an exercise to the reader. If you do end up implementing it, please let me know. I’m sure I’ll get around to it eventually, I just have finals coming up in the next week so it’s low on the priority list.

Anyway. That’s what I’ve been up to lately. I’m working off and on on doing a Tetris clone, and I’ll probably eventually get to Space Invaders. Maybe not with this library though. I’ll probably pick up something else (maybe a new language). Maybe I’ll go back to OpenGL or DirectX if I’m bored enough (and in a slightly masochistic mood). For those who are interested, the code is uploaded here. Comments and edits appreciated. Thanks for reading!

Happy Holidays!

Posted on December 25, 2009 by Eric

Merry Christmas and Happy Holidays from those of us at int main()!

Testing Google Public DNS

Posted on December 4, 2009 by Sam

In the spirit of testing things before concluding anything, I decided to test Google’s new Public DNS service against OpenDNS, 4.2.2.2 (a DNS server owned by Level 3), and the DNS servers on my network.

To test the service, I modified the excellent script created by Manu J.

#!/bin/sh
 
cur_dns=`cat /etc/resolv.conf | grep "nameserver" | tr -cs '0-9.' '[\n*]'`
 
for i in "lifehacker.com" "facebook.com" "manu-j.com"  "reddit.com" "tb4.fr" "bbc.co.uk" "intmain.net"
do
  for j in "4.2.2.2" "8.8.8.8" "208.67.222.222" $cur_dns
  do
    echo "\n$i\n$j"
    for k in $(seq 1 100)
    do
      echo `dig @$j $i | grep Query | awk -F ':' '{print $2}' | tr -cs '0-9' '[\n*]'`
    done
  done
done

My two changes were to grab the DNS servers defined in /etc/resolv.conf and to query each service 100 times. Of course, the only downside to this test is that it does not account for the DNS server caching the result of repeated queries. This effect shows up in a few of the graphs (included below).

Google’s DNS service is very consistent in speed, but is also consistently slower than any of the other servers tested. Google’s DNS service also shows very little difference with repeated requests, except for the lookup of intmain.net, where the first request took significantly longer than the others. Similarly, Google’s DNS took over 2 seconds to respond to a request of reddit.com. The final ordering is as such: the fastest in most cases was the DNS servers local to the network (except for uncommon sites, which took between 100ms and 150ms for the first request), followed by 4.2.2.2, followed by OpenDNS, and trailed by Google Public DNS.

I encourage you to perform the same (or similar) tests on your own computers and share the results. It’s very hard to tell if the differences in response times are caused by latency or lookup time, but it is clear that the best DNS servers for me to use are the ones local to my network at UCLA.

Paul Eggert speaks at UCLALUG

Posted on October 31, 2009 by Sam

Sorry for this being a little late, but Paul Eggert came and spoke to the UCLA LUG and interested parties this past Wednesday.

Eggert spoke about several things, including how he became involved with free software, his take on the free software community, how to get involved in free software, and projects he thinks would be great to have done.

Eggert mostly became involved with free software as a result of what he calls laziness. Essentially, he got tired of re-patching emacs to work on his (unusual) architecture, so he started submitting patches to Stallman. From there, he just continued submitting patches.

Similarly, Eggert thinks that the best way to get involved in free software is to just start contributing. In order to get noticed, he recommends that people pick “medium-sized” patches; not something small enough that another person could do in 15 minutes, but also not large enough that it makes any major changes. An example of a “medium-sized” project would be patching to take advantage of multi-core systems. Since most programs currently are designed with a single-core architecture in mind, some significant improvements in speed could be obtained by moving it to multi-core. Doing something like this would help to build one’s reputation in the meritocracy of the free software community.

In terms of the future, Eggert thinks that we need new languages to properly take advantage of multi-core. In particular, he mentioned projects like Hadoop are steps in the right direction. Additionally, he thinks that the current shell is too complicated for non-trivial tasks.

Anyway, happy halloween!

Paul Eggert is coming to UCLALUG!

Posted on October 25, 2009 by Sam

The below information is from the UCLA Linux Users Group.

All Engineering students — particularly those in CS — are invited to hear
Professor Paul Eggert speak on Open Source software, how he got involved over
his career, how he has contributed. The GNU Core Utilities project includes
such all-important programs as “ls”, “cp”, “sort”, “echo”, “cat”, and many more.

Wednesday, October 28, 2009
6 PM
Boelter Hall 4760
Details: http://linux.ucla.edu/sean/eggertflyer.pdf

Paul Eggert is a lecturer in the Computer Science department here at UCLA. He
teaches operating systems, programming languages, software development, and
more.

A .vimrc Discussion

Posted on October 14, 2009 by Eric

So, I’ve recently converted to using VIm. Textedit irritates me to no end, and I don’t want to pay money for Textmate. I decided I would post my .vimrc file up here and talk about it a little bit. For those who just want to read the file, it’s attached at the bottom of the post. Snippets of code follow, however.

map <space> /

All you VIm users out there know how to search for text – this enables me to search with the space bar, which feels more natural and quicker than having to type a special character.

set nocompatible
set number
set columns=80
set ruler
set background=light
set wrap!
syntax enable

This turns off emulation of bugs from Vi, enables line numbers, restricts my window to 80 columns, displays some basic information about where I am on a line, tells VIm to use fonts optimized for a light background (corresponds with my terminal colors), turns off word wrap, and turns on syntax highlighting. These options are all configured for programming.

set showmatch
set ignorecase
set hlsearch
set incsearch

This is extremely useful for searching in a file. The first line highlights matching braces, which is very nice for nested statements and complex conditionals. It also makes searching case-insensitive, highlights search matches, and starts searching with the first letter that you type. If you pay close attention when searching you only ever have to type the minimum amount of letters to find what you want. I find this greatly speeds up moving through a document.

set autoindent
set smartindent
set tabstop=4
set shiftwidth=4
set expandtab

These settings tell VIm what to do with tabs and indents. The first two lines tell the program to format indents according to the file type. As long as you’re using a C type language, this works extremely well. The second two lines tell VIm to use 4 spaces when the tab key is pressed, and the final line expands all tabs into spaces. This helps remove compatibility problems between tabs and spaces.

set vb t_vb=

This just turns off those pesky beeps when you enter an invalid command. Instead, the screen flashes for an instant. Much nicer in my opinion.

set gfn=BitStream\ Vera\ Sans\ Mono:h14

This sets the default font for the editor – Monaco Size 10. My current favorite programming font on OS X. Anyway, that’s a bit of a discussion about my .vimrc. The full file is below for anyone who wants to read the whole thing or copy/paste it for their own use.

".vimrc
"Author: Eric Hertz
"Date: 10.14.2009
"
"This is a configuration file for VIm, the terminal text editor. Feel free
"to use this however you wish.
 
"Key mappings
map <space>  /
 
"Interface settings
set nocompatible
set number
set columns=80
set ruler
set background=light
set wrap!
syntax enable
 
"Search settings
set showmatch
set ignorecase
set hlsearch
set incsearch
 
"Indent settings
set autoindent
set smartindent
set tabstop=4
set shiftwidth=4
set expandtab
 
"Audio settings
set vb t_vb=
 
"Font settings
set gfn=BitStream\ Vera\ Sans\ Mono:h14

AudioGuardian

Posted on October 13, 2009 by Eric

Hey all,

My name is Eric, and I’ll be one of your regular authors here on int main(). You’ve probably already read a little bit about me from the post that my friend Sam put up earlier, but I’ll start with a quick introduction and background . I’m a second year Computer Science student at the University of California, Los Angeles. I consider myself well-versed in C, C++, and Java, primarily. I also enjoy (if that’s the word) working with assembly on occasion (I’ll post a discussion of some assembly topics later on). Anyway. That’s a little bit about myself. I’d also like to state here that if any of our readers have side projects that they are working on and would like an extra set of eyes or hands, feel free to email. Now that I’ve dispensed with the introductory remarks, let’s dive right into today’s topic.

I feel that as a reader, I would be hesitant to read and trust someone’s opinion on things unless I knew that they actually had some experience with the things that they write about. To that end, I’d like to start this blog by talking about a program that I was a developer on – AudioGuardian. This begs a bit of background information, I’m sure. This project started as part of a competition back in February 2009. I participated in SS12 put on by ProjectPossibility, an organization aiming to make technology more accessible to the disabled community. AudioGuardian was originally named MobileSoundNotifier, and its purpose was to alert hearing-impaired users of hazards in their environment. I will append links to the project’s webpage, the project wiki, and the SVN if any of our readers would like to see some of my “production” code. I quote that because it’s definitely hacked code – this project was completed over the span of approximately 30 hours. From scratch. With that said, here’s the links to the project information:

Project Webpage
Project Wiki

The SVN is linked from the webpage in the bottom right hand corner, if any of you enterprising developers would like to take the project and work on it yourself. It is licensed under the GPL, so keep that in mind. .

I guess you can’t really fork this project without knowing a bit about how we actually designed and developed the program. Coupled with the fact that this is a CS blog and not a self-promotion blog, I will now move into a technical discussion of the program. I’m going to keep this as high-level as possible so it will appeal to all audiences. Let’s get to it.

This application is built using J2ME, which is the Java 2 Mobile Edition. It has most of the capabilities of the full Java language, but it’s missing some key features. It does not support the Swing environment, so we used the built-in J2ME graphics library to build a primitive GUI. The programming paradigm is event-driven, like the majority of Java programs. A control loop listens for commands and acts appropriately. The basic application logic should be simple to follow. But that’s all academic and really not what you’re here for. Let’s get into the problems with working with audio.

The heart of this program is an audio analyzer. It listens to the surrounding environment and throws alerts when it detects sounds deemed dangerous by either us (the programmers) or the user. Those of you with a physics background may have heard of a discrete Fourier transform before. If so, you will know that this is a complex wave analysis algorithm used to translate a signal from the time domain to the frequency domain. This was important for our application because we cannot use the time domain to perform sound matching. The only correlating factors between sound waves are amplitude and frequency, which we have to use a DFT to extract from the data stream. Sounds simple, right? Without looking at any code (you can download the code yourself and look at it, it’s too long to post here), let’s discuss the issues here.

All microphones are not created equal. Every mic has a different sensitivity and different DC offset applied to the raw data stream. This was a problem for us, since we were doing development across different laptops with different microphones. To that end, we decided to build a calibration function that listens to the ambient environment and basically filters the offset and all the outside noise. This also had the unintended side effect of increasing the accuracy of the matching function. It also built cross-compatibility, so our application will work with any microphone out there. The program also had some problems processing data streams in byte array form. The Recorder class in J2ME had a nice little habit of including the file header when it passed the data to a byte array. This then caused garbage to be passed to the graphing function, which caused some serious inaccuracy and lag time in sound recognition. To fix this, we had to strip the file header ourselves. I’ll leave it to the reader to read the code and see exactly what we did.