Welcome to Effectively Reading Academic Papers

One valuable lesson to learn earlier in your graduate program is to effectively read academic papers. Your undergraduate study may have relied upon textbooks and lectures, and may not have required or presented many papers. Research is presented in this format, so having an understanding of how to approach papers is crucial. The following examines a paper describing a recent paper on security, both highlighting important information to extract from the paper, and a roadmap which students can hopefully use as a template for how to extract benefit from an academic paper.

The example paper used is the TelepathWords paper, which describes an algorithm and system for guiding users to choose more secure passwords. The paper is available on the web (https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/TelepathwordsUSENIX2014.pdf).

The first thing to note is that the paper is 17pp long - which is slightly longer than average length for the papers used in the AOS class (although < 1/2 the size of the MCS paper). And the subject material is security, which is touched on in Salzer (et al), and the paper security in the Andrew file system.

The first page is a cover sheet, giving the authors names, and organizations (CMU and Microsoft Research). Since the paper was presented at USENIX, that is interesting (relevant for AOS).

The Abstract tells what the paper is about. Reading the abstract, we find that the paper presents Telepathwords, which predicts the next character a user may type as they enter a password. Human subjects were studied to compare the system to password composition rules.

The Introduction explains the current solutions, identifies weaknesses, composition rule policies feel (and are) arbitrary and capricious, attempt to compel users to choose better passwords (not common or weak) These rules were created > 20 years ago, and the assumptions have only recently been tested.


The purpose of Telepathwords is to clarify the measurement of good passwords, and guide users to create more secure passwords. Telepathwords makes predictions as the user enters the password, and informs the user of predicted next character(s). A Mechanical Turk (human) study measured passwords formed using Telepathwords, and compares the results to existing rules-based password policies. The authors claim the system promotes better weakest passwords than rules-based approaches.

The Introduction (and Abstract) provide a guide (map) to the paper contents. So we know that the paper will explain both how the algorithm works, and report on study results. At 16 papges (less cover), we can expect 4-5 pages of algorithm explanation. The results claim better performance than existing rules-based policies, which an interesting and valuable result.

The Design and Implementation section starts by describing the User Experience. Telepathwords presents a predictive display and feedback bar (figure provided). The prediction display predicts the next character(s) (1-3) based upon the underlying algorithm, and relates to autocomplete (a common UI feature). The undesirable nature of the predictions is highlighted (prohibition/universal NO symbol). An explanation why the predictions are poor choices is presented. A feedback bar aligned with the entered characters shows which characters are good (green check) or poor (red crossout). Common character substitutes are detected (thus P@ssw0rd is shown as a poor choice).  Profanity handling was handled and explained.

The Description continues with a section on Architecture. This 1/2 page is important, so we read carefully. A client-server architecture uses Javascript front-end end to display predictions. The entire 1.5GB language corpus is kept on the server. This differs from other password meters, so this choice is explained. One justification for retaining client-side is security, but the current web architecture must transfer the secret in plaintext-decryptable format. Telepathwords compresses and pads to common length, transporting over HTTPS (SSL). Network latency are small compared to expected user response time, and can be mitigated by moving servers closer to users.

The Prediction algorithm is the core of the paper, so extra focus is needed to ensure we understand the algorithm. A trie data strucure is used to map strings to likelihood scores, keeping predictions in likelihood order (only need 3 highest). The predictor finds all predictions, and ranks them, returning the best predictions to the user (discarding those below a threshold rank). Telepathwords ahs predictors for common character sequences, keyboard patterns, repeated and interleaved strings. The language corpus is composed into a space efficient completion trie, using browser search and RockYou datasets, and expected likelihood is calculated from prefix length and frequency. Completion tries are similar and adapt to common misspellings and typos. Transpositions impose a penalty as they occur with lower frequency. Common strings are detected anywhere in the query, using a window of completion node tries for each possible starting position, and track trie node for each possible suffix. Two special windows are tracked, one when only letters are entered, the other only when numbers are typed, and these special windows detect poor passwords such as "pass1234word". A table maps common character substitutions (3 for e, $ for s, 0 for o) is used, as these common substitutions do little to increase password entropy.

Study figures 3, 4, 5 and 6 as they illuminate the algorithm, and help to explain how the algorithm works. Figure 3 illustrates how the trie maps strings to likelihood scores, and nodes with higer scores appear to left of lower scoring nodes. Figure 4 shows the sliding window used to walk the trie for each suffix of the query string. Figure 5 explains the common character sequence predictor walks the ancestry chain to find better predictions. Figure 6 illustrates the keyboard-movement predictor (from the QWERTY keyboard).

The analysis of each password prefix of length=n begins with analysis of its length=n-1 prefix. Analysis cost grows at least linear with password length. Recent analyzed query strings are cached in memory. Cache is small relative to the 1.5GB language corpus, which is stored in main memory (SSD is fast enough, but servers used during trial did not have SSD).

The keyboard movement predictor detects passwords from sequences formed by adjacent keys. A keyboard model maps characters to x,y (row,col) coordinates, and represent a password prefix as a sequence of key positions. Keyboard wrap is considered, and only QWERTY is considered.

Repeasted strings are detected by examining each possible suffix of length=n and looks for repeated sequences. For example, "pwabcdefabc" finds "abc" repeated, and predicts "def" next. Interleaved strings such as "ppaasswwoorrdd" are detected by splitting even and odd indexed subsequences, and runs other predictors against those sequences.

A section on Telemetry is presented next, and though worth reading, is not crucial to the algorithm, but more about the measurement for the study. An explanation of the caution regarding storage is presented.

A section on System Limitations explains that the language corpus is US-centric and dated, and suggests a real product would require update for new lexicon entries. Additional corpa for other langues (cultures) would be needed. Not mentioned in the paper is that to be effective the corpa would need to mirror that used by crackers to exploit passwords. Reversed character sequences ("gfedcba" for "abcdefg") are not detected, unless the reversal appears in the language corpus (e.g. "drowssap"). Adding a reversed corpus wold enable reversal detection. User behavior is not measured to detect adaptations to the Telepathwords algorithm. Crackers have exploited the behaviors promoted by human behavior and Rules-based polities to develop exploits.

A section on Deployment explains how the Telepathwords system was deployed, which would be important to researchers wishing to replicate the experiment. Pragmatically, as a student studying the algorithm, this section would only be important as it speaks to credibility, and how the student might design experiments for their own research projects. Thus important to read, but to learn effective ways to implement experiments to support your own research findings. Reading about the testing, it occurred that using Telepathwords to guage the strength of breached password databases (e.g. Yahoo Voice), would be a good measure of the prediction strength of Telepathwords.

The Deployment section continues with a review of the Data Collection methodology (again, same comments are relevant).

The Experimental Methodology section segues into information relevant to researchers and those wishing to evaluate the results as consideration for using the algorithm themselves. Again, understanding this section would be informative to designing and conducting your own experiments, and useful for evaluating the results. This section explores the human behaviors analyzed. Here one might realize that the problem being solved is how to make humans adapt to increasingly clever crackers, rather than trying to understand and augment human behavior. One has gained understanding of the problem, solutions (both prior and the one presented), and might start to conceptualize other ideas (here is where you make notes for your own possible research ideas).

The Experimental Results and Analysis section presents the statistical methodology (useful to review or to leverage for your own research), but not informative to learning about the technology (Telepathwords) presented. Human behaviors are measured, so the approach may be useful for UX/UI research, cognitive research.

The results and the section on Sentiment suggest that user acceptance would be good, and the system would be effective are reducing the number of weak passwords which evade Rules-based systems. Figure 14 shows that users would view the passwords created using guidance from Telepathwords would be as or slightly more secure that alternative rules-based policies.

The section on Security Results presents the idea that improving the weakest passwords is an important factor to protecting an organization from penetration. No reference is quoted to support this claim. Improving the floor of security to some acceptable level would seem important, but ensuring a strong minimum security across the mean password based seem to be the preferred goal.

he common most effective attack vector is to obtain the encrypted password database, generate potential passwords, and search for a match in encrypted space. The algorithm described in this paper would generate less predictable passwords, but this most common vector is not analyzed. Nothing about spectral qualities of the Telepathwords guided passwords seems any better than a generated password, and the psychology of choosing passwords is not addressed (unlike the XKCD article).

The section on Releated Work examines the historical and current research on the topic, and provides guides to other related research. This section is most useful for doing further exploration on the same topics. The Reference section offers the same utility, providing the actual references to perform further study.

The Conclusion explains that Telepathwords provides users better insight into the quality of their passwords that other systems, and provides stronger passwords that systems which do not employ dictionaries to filter weak passwords (not surprising). Users found the tool difficult or annoying.

Welcome to Advanced Operating Systems

After I graduated from college with a BS in Mathematics (minor in Computer Science), I planned to pursue graduate study (I was smart, capable, and had graduated with honors). Graduate study seemed reasonable.

My first graduate course was at Georgia Tech, CS-6241 Compiler Construction, nearly 30 years ago. But circumstances (work schedules, deadlines, distance, etc) dissuaded me from continuing my graduate study. And Life happened. I had a wife, children, a mortgage, car payments, etc.

time passed...

But after a long career designing and writing software, I still retained my curiosity and my love of learning. Circumstances finally converged to present me with both the opportunity and motivation to return to academia, and return to graduate study. Georgia Tech had partnered with Udacity (and AT&T) to create a new on-line program, an MS in Computer Science, crafted to the needs of students who could not suspend their lives to pursue advanced education.

I admit that I was both skeptical; would the experience offer the same quality and comparable experience to an on-campus program? And I was intimidated; I had not been in a formal class setting in a long time; would I face challenges that would overwhelm me? This was a huge commitment.

Could I handle the rigor?
Could I handle the workload?
Could I handle the schedules, the deadlines?

Realize that I have a full-time software development job; I have work deadlines.
Realize that I have a family commitments (wife, children in high school and college).
Realize that I have financial demands and time commitments.
Realize that I would like to enjoy some leisure.

The program offered a variety of interesting courses and several course specializations. Computing Systems promised to teach about Operating Systems, Networks, Security, and Theory, while Machine Learning offered courses in Machine Learning, Artificial Intelligence, and Data Visualization. Perception and Robotics promised Visual Processing, Artificial Intelligence, and robotics control.  But scheduling presented challenges. Several courses were full. Would I be able to secure a core course and make progress?

The first course I chose was CS-6210 Advanced Operating Systems, also known as AOS. This course has a reputation as a course that both challenges a student's ability and requires significant effort. The course was a formidable re-introduction to academia. The course required lectures, tests, reading papers, and projects.

The lectures were good, and the covered the material. One key piece of advice I must share is that you need to keep on pace watching the lectures. But do not just watch the lectures in a perfunctory manner. Understand the material. Own the material. Ask questions on Piazza (the Q&A forum provided for each class, where TA's and the Instructor answer student questions). The discussions keep pace with the syllabus, so you need to keep current. Consider watching the lectures twice (watch ahead, and watch on schedule).

The papers were hard. I had read academic papers and RFCs for work. I had written documentation, reports and white papers on various topics. I found myself reading nearly 40 academic papers (~3/wk) covering an array of OS topics, ranging from process scheduling, memory allocation, segmentation and paging, TLB and address translation, inter-process communication, monolithic versus lightweight kernels, virtualization, network communications, security, distributed file and memory storage, distributed synchronization, content distribution networks, and more. These papers spanned important points of OS development stretching over nearly 40 years of advances. I found some papers unclear, and further investigation and reading were needed to clarify concepts. Some concepts were easy, while others were deep.

Understand that my career spanned many of the developments studied in AOS. I had written programs for several of the example OS studied, and had knowledge of  MS-DOS, BSD Unix, SysV Unix, Mach, Solaris, Linux, VMware, Xen, NFS, RPC, Sockets, etc. Some of the material was familiar. Some of the material was new.

Reading these papers took time. I needed too much time. Something needed to change. I had to learn how to read academic papers more efficiently, how to find, highlight, and extract important information. I  had to learn how to understand and assimilate these concepts. All this while completing the other assignments. My advice is to make a schedule, and keep up with the readings. Establish a pace for yourself.

The projects were hard, they took time and effort. The first project was to write a C program to address the Dining Philosophers' problem. We had to understand the problem (resource contention and deadlock), and how to solve the problem (break one of the four conditions leading to deadlock). Each student had to build a working program. And submit by the deadline. But that was only 10% of the first project. The other 90% was to build a thread package (gtthreads), but not using pthreads. Students had to find the system calls to make a new process context, switch between contexts, and perform scheduling. We had to ensure that each thread got time. And we had to avoid deadlock. The project was challenging and took time (I probably spent 50-60 hours working on the project).

The class shared their understanding of the requirements. Many students contributed test programs to validate each of the requirements we identified. The students used Piazza and github to share their understanding of the requirements and test harness. The projects were individual, but we collaborated to create the tests.

This is a graduate course at a premier university. Dr. Kishore, the professor, expects you to actively participate in learning, to seek and discover the information you need (which is provided in the papers and lectures).

The tests were proctored (Proctortrack, get comfortable with it before the midterm), and timed. The questions were brief, but required knowledge of a lot of material. Keep up with the lectures, and read the papers (efficiently), and you will know most of the material. The tests require knowledge, and you want to learn the knowledge.

I learned a tremendous amount in AOS, and have completed two more OMSCS courses.

I am now a TA for AOS, and I look forward to sharing a rich learning experience.
I survived AOS. You will survive AOS.
Enjoy the journey.

(I will share more of my experiences from AOS and OMSCS in upcoming posts).
---

Georgia Institute of Technology in Atlanta, Georgia is a premier university which offers an excellent education, and is considered one of the top engineering schools in the country.

OMSCS (On-line Master of Science in Computer Science) is a program which offers courses completely on-line, delivering education to over 4000 enrolled MS-CS students. The courses use the Udacity learning portal, delivering lectures, quizzes, and automated grading platforms, and combined with technologies including T-Square, Piazza and Proctortrack (among others) delivers a rich learning experience comparable to the on-campus program, yet unconstrained by time or location.

Here are the OMSCS courses