Denyhosts は ssh でのログインログを解析して、不正アクセスを検知すると自動的にそのユーザーからの ログインを拒否するように /etc/hosts.deny を書き換えるというものでした。
しかし Denyhosts は長い間放置されていたせいで、 Debian のパッケージから削除されてしまった模様です。 その関係で、Ubuntu 14.04 でも denyhosts が消されてしまいました。 Package denyhosts in Ubuntu Trusty Tahr is deleted: temporary or forever? というわけで、denyhosts から同等機能を持つ fail2ban に乗り換える事にしました。