This is my Digital System Design course project, collaborated with James.
Abstract
Artificial Neural Networks (ANN) are non-linear statistical data modeling tools, often used to model complex relationships between inputs and outputs or to find patterns in data. In this project, a generic hardware based ANN is designed and implemented in VHDL. This three-layer ANN is implemented entirely with 32-bit single precision floating point arithmetic to guarantee flexibility and accuracy for its wide range of applications. The ANN supports reconfigurable numbers of perceptron per layer as well as supervised learning through back propagation. Mean squared error is used to measure the quality of learning as part of the Built-in Self-Test (BIST). An rudimentary example application is implemented to demonstrate the capability of the ANN on an Altera DE2 FPGA board. The example application is a fully functional pattern recognizer, built by utilizing the ANN. This classifier is trained to identify letters on a 4x4 binary grid populated by a user through 16 toggle switches. The most probable class suggested by the ANN is displayed on a LCD screen.
Instead of building the map server as a player server plugin, I am now using memcached as my distributed map server.
Memcached allowed much faster access of map tiles. I also implemented tile lock so that multiple player plugins can update the same portion of the map at the same time.
Probability mapping, red means traversable space and blue is obstacle.
After growing the obstacles, the probability map is converted into configuration space map. This map can be easily used in global path planning. I also created a buffer zone near obstacles so the path planner will try to avoid those high cost area.
Some recent work on AMOS mapping that I'd like to share:
Variance mapping outdoor
Elevation mapping indoor
Elevation mapping indoor
Variance mapping indoor
Visual mapping indoor
Right now, the mapping is done as a series of player plugins. But the problem with player is its slowness in transmitting map tiles. So future release will use a distributed memory cache (memcached) instead.
Should have posted this more than a year ago. This was a project for my grad-level Parallel Computing I class with Professor Alan Kaminsky. The goal for this project was to run massively parallel algorithm on cluster machines at RIT Computer Science Department to provide better final exam scheduling for students with different preferences and course schedules.
RIT has approximately 16,000 current students and offers roughly 3,000 sections of courses per quarter. The problem of generating a comfortable final exam schedule for all students becomes fitting 3,000 final exams into 20 time slots during the finals week. The number of possible permutations, 20^3000, is astronomical. We hope to show that a parallel approach will offer a significant performance benefit over a sequential approach for this problem.
The final exam scheduler is an application that will to compute an optimal final exam schedule for RIT students. The program will use a list of course offered by RIT and cross-reference them with the class registration of students. In order to find the best schedule, we will devised a ranking algorithm to score each schedule on various criteria and the resultant schedule should be close to an optimal solution.
Source and Report We used Simulated Annealing, Genetic Algorithm, and a plain permutation approach as baseline. Source and report available at our repository: https://github.com/ziyan/final-exam-scheduler
Zachery Shivers and I rushed this project out in the past week for the TI MSP430 Ultra-low Power Challenge. What we've achieved so far is a secure wireless door lock that allows you to unlock your door remotely via your RF-enabled TI eZ-430 Chronos watch.
Abstract Using the new TI eZ430-Chronos sport development watch, which is based on the CC430, we created an electronic door unlock device. The watch communicates wirelessly to lock and unlock the door after given a secret password (a sequence of taps on the watch's 3-axis accelerometer). This system demonstrates an ultra-low power consumption wireless system using TI’s MSP430 architecture, achieving estimated battery lifetimes of over 4 years on the watch and over a year on the door.
Hardware The eZ430-Chronos wireless development kit is a powerful evaluation kit created by TI. This evaluation kit allowed us to program the watch very quickly with the provided debug and programming via USB dongle. The door hardware was custom built around the CC1111EMK868-915 Evaluation Module Kit, which uses the CC1111F32 wireless System-on-a-Chip.
Power Consumption Estimates The estimated duty cycle of watch is 10 unlock cycles per day. The estimated duty cycle of the door is 30 unlocks and 30 locks per day. Using the built-in 220mA coin cell battery, the watch that consumes 0.131mAh per day will function without a battery change for approximately 1,679 days or 4.6 years! Using the four 2500mAh, 1.2V batteries in series, the door that consumes 4.03mAh per day will function without a battery change for approximately 620 days or 1.70 years!
Security In a sense, our wireless door lock solution is even more secure than the traditional method of unlocking doors using keys. To unlock the wireless door lock, the user not only has to have a previously paired watch, but also has to know the secret knock sequence to the particular door. Here, security is achieved by requiring a combination of something you have as well as something you know.
Something You Have – Texas Instrument eZ-430 Chronos Watch On the watch, we store information about up to 21 paired doors in a simple database. The information includes a unique 16-bit door ID and a 128-bit shared AES key agreed with the door upon pairing. Each watch and door pair has its own designated shared key and unlock sequence. Using the shared key, the door and the watch can communicate securely.
Table 2. Typical door-side database (up to 68 entries stored in flash)
Upon user’s request, the watch can initiate a key renewing process that would allow a new 64-bit partial key to be generated. This new partial key will be encrypted using the old key and sent to the door. Door will combine this new partial key with part of the old key. Doing this process twice will rotate a completely new 128-bit key between the watch and the door. We recommend the user renew their partial key every month. To prevent repetition attack, we implemented a session token system. When initiating a door unlocking, key renewingor sequence changing process:
The watch will send an unencrypted SYN packet to discover nearby doors
The door will receive the SYN request and looks up the watch in its database and find the shared key
The door will generate a 32-bit pseudo random number known as the session token for the particular watch
The token is encrypted using the shared key and sent to the watch in a SEC packet
The watch then decrypts the SEC packet; verify its validity by looking for a pattern in the decrypted message; and save the token for the remaining of the session
From now on, during the session, the token will always be included in the encrypted part of the packet and both the door and the watch will verify each message using the token
Upon success completion of the operation (e.g. successfully unlocking the door, renewing partial key, or changing the knock sequence), the token will be discarded by both ends and become invalid
If the attacker tries to repeat the door unlock sequence by recording the radio transmission, the attempt will fail due to an invalid token. Neither can an attacker disrupt the session by requesting a session token on the watch’s behalf, because the session token will only change upon success operation or when it expires.
Something You Know – Secret Knock Sequence If an attacker gets hold of your watch that contains the 128-bit shared key to your door, it is still not the end of the world. A 96-bit unlock knock sequence is required to unlock the door. This sequence can be set uniquely for each watch-door pair. This sequence is collected by measuring the shock on the watch using the integrated 3-axis accelerometer. The user can simply and quietly tap on the watch to input such sequence.The collected sequence is then encrypted using the shared key and sent to the door in the SEQ packet for verification. The door normalizes the sequence and verifies its validity against the data stored in its database. However, normalization allows the user to tap at a different speed each time as long as each tap has consistent relative length.
Suppose we have the following simple sequence: “TAP [… pause …] TAP TAP [… pause …] TAP[… pause …] TAP”. The watch will see shock at each tap. Our algorithm works as the following:
Start the accelerometer and look for the first tap.
Found first tap, start a timer to time the pause length between the first tap and the next tap.
Found second tap, stop the timer, and store the pause length (8-bit, in 6 millisecond resolution) as the first element in an array (of size 12). Start timer again to time the pause length between second tap and the next tap.
…
If timer time out meaning the pause is too long, or the entire array if filled, we then call the sequence finished.
Now the array contains numbers that measures the length of the pauses between each tap. So for the sequence “TAP [… pause …] TAP TAP [… pause …] TAP[… pause …] TAP”, the array content will look like:
To make sure we can match the same sequence knocked at different speed, we have to normalize the sequence by scaling the longest pause in the sequence to 0xFF like this:
Now the sequence is normalized and can be compared to a previously normalized sequence for validity. A probability of match is computed based on the normalized sequences. Of course, we cannot tap a sequence perfectly, so some margin of error is allowed.
As you can see, a sequence consists of 5 taps will result in4 pause lengths. We allow up to 12 pause lengths which can be translated into 13 taps totally. The more taps your secret knock sequence consists of, the more secure your door lock will be.
The secret knock sequence is also not permanent and can be changed securely over the air upon user’s request. The door has to be put into a special mode called the “sequence changing mode” to allow nearby watches to reset their secret sequence. This can be done by holding the button on the door for at least 5 seconds. After the user taps in a new sequence (twice for confirmation), it is encrypted using the shared key and sent to the door in the PWD packet. The door will then store the new sequence in its database and exits the “sequence changing mode” automatically. Again, we recommend our user to change their secret knock sequence in a regular basis.
Potential Vulnerability No security system is perfect. We’ve hypothesized some security vulnerabilities in our system.
The biggest problem is always the initial pairing of watch and door. To pair a watch to a door, the user have to put the door into a special mode called “pairing mode”. This can be done by holding the button on the door for at least 10 seconds. In pairing mode, the door will accept RAW packets which are used to exchange initial keys. The user can initiate a pairing process from the watch. The watch will collect random bits using the accelerometer and construct a 128-bit shared AES key. This key is transmitted unencrypted in the RAW packet over the air to the door. The door will accept the key and store it in its database only if it is in pairing mode. The door then acknowledges the watch about the success completion of the pairing, and exits the dangerous pairing mode automatically. Pairing mode can also be used to reset the 128-bit keys once those keys get out of sync between the door and the watch. This out-of-sync state is a rare state which will happen when an acknowledgement packet is lost during a key renewing process. We try to minimize this risk by always sending multiple ACK packets.
As you can see, the door is considered “naked” when it is put into pairing mode. A potential solution to this problem is to decrease transmission power in pairing mode such that the watch has to be very close to the door. Another potential solution is to run a Diffie-Hellman key exchange process and requires the user to input a pre-shared secret in order to pair with the door. The secret can be in a form of tapping or button press sequence.
Update: Hardware Revision 2 Zack has just completed the PCB design for hardware revision 2. In this revision, we got rid of the reed switch to detect door close. We will have two IR sensors, one pointing out from the side of the box for detecting door close, the other pointing into the apartment for detecting approaching person and unlocking the door when the person gets close enough. A buzzer is also included to produce battery low voltage warning and other messages.
