Date of Award


Degree Type


Degree Name

Doctor of Philosophy (PhD)


Computer Science

First Advisor

Ninghui Li

Committee Chair

Ninghui Li

Committee Member 1

Elisa Bertino

Committee Member 2

Dan Goldwasser

Committee Member 3

Robert W. Proctor


Password-based authentication is perhaps the most widely used method for user authentication. Passwords are both easy to understand and use, and easy to implement. With these advantages, password-based authentication is likely to stay as an important part of security in the foreseeable future. One major weakness of password-based authentication is that many users tend to choose weak passwords that are easy to guess. In this dissertation, we address the challenge and improve the eco-system of passwords in multiple aspects. Firstly, we provide methodologies that help password research. To be more specific, we propose Probability Threshold Graphs, which is superior to Guess Number Graphs when comparing password models and password datasets. We also introduce rich literature of statistical language modeling into password modeling and show that if used correctly, whole-string Markov models outperform Probabilistic Context Free Grammar models. Secondly, we improve password policies and practice used by websites by studying how to best check weak passwords. We model different password strength checking methods as Password Ranking Algorithms (PRAs), and introduce two methods for comparing different PRAs: the β-Residual Strength Graph and the Normalized β-Residual Strength Graph. Finally, we examine the security and usability of commonly suggested password generation strategies. We find that for mnemonic sentence-based strategies, differences in the exact instructions have a tremendous impact on the security level of the resulting passwords. For word-based strategies, security of the resulting passwords mainly depends on the number of words required, and requiring at least 3 words is likely to result in passwords stronger than the general passwords chosen by typical users.