Advanced Persistent Threats(APT) are a serious concern to secure an organization. The sophistica- tion of APT attacks is much discussed, and the recent compromising of Google, RSA and Sony using APTs has gained lots of attentions. Successful protection against APTs should complement traditional perimeter and infrastructure security measures and policies. In this paper, we show that adding APTs in our threat landscape, conventional attack graphs for realistic environments are quite dense meaning that their utility is quite limited. This density is a consequence of common, inherent vulnerabilities in conventional computing systems and network environments. Our approach is to formally define a set of vulnerabilities that we call privilege expansion vulnerabilities. A superset of privilege escalation vulnerabilities, privilege expansion refers to cases where an attacker can either earn greater privilege on the current host or use his current privilege to earn privileges on other hosts. Based on our formal definitions, we define a set of rules for adding edges to attack graphs and develop a tool that computes a closure of these rules in the graph. For two example environments, we compute new attack graphs incorporating these new edges and demonstrate the use of the tool by evaluating addressing 4 different privilege expansion vulnerabilities.