Built up handful of handy features from a bare bones (single-process, almost no syscalls) operating system.

• Implemented userspace
  • Processes, threads, page faults, and appropriate syscalls
• Implemented thread priority
  • Scheduling, timers, deadlock avoidance in synchronization primitives
• Implemented a file system
  • Inodes, path resolution, caching, and appropriate syscalls

For prospective students: this class is fun, but fun and difficult aren’t mutually exclusive.

Source | Highly Recommended Reading

CS170 (Algorithms) at Berkeley has a long tradition of handing students an NP-complete problem and holding a competition to see who can produce the best computationally tractable approximation. Guavabot rescue gave a two layered problem:

• Faulty sensing
• Steiner-tree approximation

Team “go-bears'; UPDATE Teams SET score = 0 WHERE name != 'go-bears';” got rank 23 out of 320 groups. The important thing, of course, was that countless stranded Guavabots around the world were rescued.

As with other projects I can’t really reveal my group’s approach publicly since this project may resurface in future semesters, but if you’re 1) curious and 2) not planning to enroll then let me know!

Source | Specification

Title is a mouthful but that’s what it was officially labeled as! In addition to being a programming assignment this was a major exercise in secure design, so the source also includes a design document detailing the possible attack vectors and appropriate defenses. In particular the system was designed to allow trusted users to share files with each other using a client and an insecure data server. The goal was to allow for client’s to share arbitrarily large files, update + revoke access privileges, and modify files in such a way that it would be computationally infeasible for an attacker to recover information, modify a file silently, or impersonate another user even with full control over the storage server.

Implementation relies on traditional RSA, Argon2 for key derivation + password hashing, and generous applications of HMAC. Sadly still vulnerable to Rubber-hose Cryptanalysis.

Source | Relevant XKCD | Specification

A close contender for my favorite security project. Students were handed an insecure webserver and tasked to find 7 exploits. It turns out breaking stuff is orders of magnitude more fun than making stuff!

Source | Specification

A two-stage pipelined CPU that runs the RISC-V instruction set (thanks David Patterson!). This was actually a real doozy that would take a while to list out but in summary:

• Full Arithmetic Logic Unit built from ground-up with logic gates
  • Including support for word, half-word, and byte level instructions
• Memory, branching, and instruction decoding
• 2-stage (instruction-fetch, execute) pipelining
  • And cases for all the wonderful side-effects that crop out in conjunction with branching :’ )
• Lifetime supply of unit and integration tests

Source | Specification

A fully functioning “Roguelike” game including:

• Procedural dungeon generation
• Tile engine, lighting, and special game mechanics (further details in video)
• Gameplay recording and playback

Blog Post | Source | Video ; ) | Specification

This project consisted of three main parts:

• Rasterize map tiles of backend and serve to the front end
• Modify an XML parser to convert OpenStreetMap data for the city of Berkeley into appropriate data structures on the backend
• Implement A* search to provide navigation directions

Source | Specification

Tools for developing optimal strategies for the game of Hog when complete information is available, and for approximating solutions when there is incomplete information. Includes visualization tools to watch strategies evolve between iterations. More details in this post

A full featured interpreter for the Scheme programming language written in Python. Supports all the beautiful features of Scheme including:

• Tail-call optimization
• Quasiquotes
• Macros

Source | Relevant XKCD | Specification