One of the most important things that any security engineer will be called on to do is to analyze and/or solve significant technical problems. While many of the best security engineers seem to have attained these skills by some miracle of birth, the skills can be learned and improved upon.
The domain where these skills are found most in abundance in the computing world is that of black-box or exploratory quality assurance. QA professionals are used to having to analyze and diagnose problems, and that makes their literature replete with references to the type of skills that a security engineer ultimately needs to be able to answer the question: "I just got an IDS alert... is it a false positive?"
Debugging - One of the seminal books on the subject of debugging, this book really approaches the question of debugging from the perspective of thinking about how to solve problems. It provides rules and principles that can assist you in thinking through problems more effectively.
How to Solve It - George PÃ³lya's much revered text on how to solve math problems, it's one of the most brilliant tools for helping understand problems and how to solve them. Math is the vehicle here, but what the book really teaches is a system of thinking that will help anyone... the skills in the book are invaluable tools to have in your mental toolbox.
Debugging By Thinking - Metzger's book is a personal favorite of mine - it frames debugging in terms of the greatest detectives in history, most noteably, Sherlock Holmes and Phillip Marlowe. He writes up debugging scenarios and shows how these great literary detectives would have approached the problem, and what you can learn from the different approaches. I always thought this book should be required reading for anybody interested in reverse-engineering.