Month: April 2011

Fibonacci Algorithm

Today seems to be an algorithms-appreciation day. I coded up two versions of generating the nth Fibonacci sequence. The naive one we all learn in class with an O(2^n) run time:

 

 

And then a more efficient algorithm that memoizes– run time of O(n):


 

And i ran a test to find the 40th Fibonacci number:

Sorting Algorithms

I felt like recreating some well-known algorithms in Python and playing around with them. Given a list of 700 random numbers, you’ll see how fast these algorithms performed. Proof again that they are O(n^2) for Selection and Insertion, and O(nlogn) for Merge & Quick sort.

How to Set Up Microsoft’s Kinect for DepthJS

In my first post, i wrote about how the Kinect was hacked and reverse-engineered. The Fluid Interfaces group over at MIT created DepthJS to let them surf the net by having the Kinect recognize certain gestures and motions.

After purchasing my own Kinect and downloading the source code from https://github.com/doug/depthjs, i realized there weren’t any good documentation on installation and setup.

Note: This is only for Mac OS X + Chrome. There are other versions for Windows.

Therefore, i have this post.

  1. First, click the link above and download the source code to a certain location. For the next few steps, it will be in my Desktop.
  2. Go to the Chrome browser, open a new tab, and type chrome://extensions
  3. You’ll see the following page which might include your other extensions or nothing at all. Just in case, make sure you are in developer mode. Then, at the top, click “Pack extension…”

    4.  

  4. A popup will occur. In “Extension Root Directory,” navigate to the location of DepthJS and click only on the root folder called “chrome-extension-mac”
  5. Finally, back at the main extension page, click “Load unpacked extension…” and that should be it!

Make sure the Kinect is plugged in and refresh Chrome. You also need to be at a certain distance because if you’re too close, it won’t work. Once you see the DepthJS icon in the upper right of your Chrome browser, just stick out your hand and start navigating around!

Here’s what i saw:

Notice how it detects my primary and secondary hands. Pretty neat! Go computer vision!

It’s been only 1 hour since i set this all up. I only managed to open links, but can’t get scrolling up/down to work despite my large hand motions. More on this later. Hopefully i’ll get up to speed and start contributing to OpenKinect and/or DepthJS in any way.

New Site Layout

I am approximately 75% done overhauling my new website. Integrating WordPress into my current theme was tedious, but I learned alot about the code underneath. Last few things i need to do is build a new photo gallery and build some individual project pages for my portfolio. And. Then. I’m. Done.

And here’s an evolution of my previous webpages. You’ll see the huge improvements over time!

And it’s time for a new picture. In other news, i’m also taking courses at Cal Poly Pomona to kill time. I’m also working on iPhone and Ruby on Rails projects too. Cheers for now. I will update more later!

Fermat’s Little Theorem to Determine Primality

01110000 00111001 00110000 01111000 – day 3: done

On another note, i’ve been playing with Fermat’s Little Theorem. His Theorem is a way to determine if a number, N, is a prime without factoring.

Fermat’s Little Theorem:

if p is prime, then for every 1 ≤ a < p, then a^(p – 1) ≡ 1 (mod p)

I tested this by writing some code in Python:

#Fermat’s Little Theorem in Python

from math import exp
import random
number = input("Give me a number: ")
num = int(number)
a = random.randint(1,num-1)
b = a**(num-1)
if (b % num) == 1:
print("We have a prime!")
else:
print("Sorry, not a prime!")

#End of code

Of course, in math theory, there are some numbers that still pass this test, known as Carmichael Numbers. An example is 561 = 3 * 11 * 17 which fools the Fermat test. The solution is to merely run the test several times to ensure primality!

Security Design Principles

I’ll be blogging about the principles of Security Design and such! These are notes from my security course at Berkeley.

Three Cryptographic Principles
  1. CONSERVATIVE DESIGN -Doug Gwyn says “Systems should be evaluated according to the worst plausible security failure, under assumptions favorable to attacker.”
  2. KERKHOFF’S PRINCPLE- Cryptosystems should be secure even if the attacker knows all the internal details and algorithms. The only secret is the key. If your secrets are leaked, it’s easier to change the key than to change the algorithms, etc.
  3. PROACTIVELY STUDY ATTACKS- devote considerable effort to try to break your own systems to gain confidence in its own security. In the game of security, the attacker gets the last move and it will be costly to repair a system after wide deployment. Hence, pay attackers (black hats or tiger teams) to identify attacks before the bad guys do
Thirteen Principles for Secure Systems
  1. Security is Economics– it doesn’t make sense to buy a $10k firewall to protect $1k worth of trade secrets. We should focus our energy on securing the weakest links and attackers follow the path of least resistance, ie. there’s no point putting an expensive deadbolt on a screen door because the attacker can just rup through the screen and step through
  2. Least Privelege– minimize how much privilege you give each program and system component, ie. only enough to do its job. It doesn’t reduce failure probability, only expected cost of failures because the less privilege a program has, the less harm it can do. BIGGEST EXAMPLE is Windows allowing users to log in as Administrator the entire time.
  3. Use Fail-Safe Defaults– similar to firewalls and denying all access, you want to do the same by denying all access and explicitly allow certain permissions. BIGGEST EXAMPLE: if a packet filter fails, no packets are routed (fail-open and fail-close, ie. hospital example)
  4. Separation of Responsibility (movie theatre tickets)– split the privilege so that no one person has complete power (more than one party must approve before access is granted).
  5. Defense in Depth– use multiple redundant protections so that all of them must be breached to endanger a system.
  6. Psychological Acceptability– users must buy into a security model. [????? uh, see lecture notes] The point: no system can remain secure for long when all its users actively seek to subvert it. System Administrators will not win
  7. Usability– just like from the midterm, security systems must be usable by ordinary people and asking users to make complex/subtle security decisions is not useful (ie. Windows Warning pop-ups. users will always click “OK” just to make the box go away)
  8. Ensure Complete mediation– when enforcing access control policies, ensure that every access to every object is checked. BIGGEST EXAMPLE: Google’s caching (?????)
  9. Least Common Mechanism– original assumptions may have changed! BIGGEST EXAMPLE: Facebook. Started out at Harvard, so which Harvard student would honestly want to hack it? Now that FB is open to the public, the old assumptions no longer hold true.
  10. Detect if You Cannot Prevent– the title says it all. Be able to identify the perpetrator! Forensics are your most important tools: keep audit logs so you can analyze break-ins.
  11. Orthogonal Security– this means “transparently” to the rest of the system bc it’s useful in protecting legacy systems. Also allows us to improve assurance by composing multiple mechanisms in series
  12. Don’t Rely on Security Through Obscurity–as a system becomes more popular, attackers will have more incentive to attack it. It is impossible to keep a system design secret from a dedicated, skilled adversary bc every running installation has binary executable code that can be disassembled. Of course, disclosing design doesn’t improve security either (ie. Opensource applications)
  13. Design Security In, From the Start– retrofitting security in an existing application is difficult b/c you’re stuck with the chosen architecture and you can’t easily change the system decomposition to ensure the above principles. Backwards compatibility is often painful because you need to suppose the worst security problems of all your previous versions.

 

MergeSort


Fatal error: Uncaught Error: Call to undefined function is_post_publicly_viewable() in /services/http/users/m/mattkc/blog/wp-includes/media.php:1043 Stack trace: #0 /services/http/users/m/mattkc/blog/wp-includes/shortcodes.php(346): gallery_shortcode() #1 [internal function]: do_shortcode_tag() #2 /services/http/users/m/mattkc/blog/wp-includes/shortcodes.php(248): preg_replace_callback() #3 /services/http/users/m/mattkc/blog/wp-includes/plugin.php(213): do_shortcode() #4 /services/http/users/m/mattkc/blog/wp-includes/post-template.php(230): apply_filters() #5 /services/http/users/m/mattkc/blog/wp-content/themes/twentyfifteen/content.php(34): the_content() #6 /services/http/users/m/mattkc/blog/wp-includes/template.php(557): require('/services/http/...') #7 /services/http/users/m/mattkc/blog/wp-includes/template.php(514): load_template() #8 /services/http/users/m/mattkc/blog/wp-includes/general-template.php(171): locate_template() #9 /services/http/users/m/mattkc/blog/wp-content/themes/twentyfifteen/archive.php(42): get_tem in /services/http/users/m/mattkc/blog/wp-includes/media.php on line 1043